IntroSort — VisualAlgorithms Docs

How it works

Starts as quicksort, switches to heapsort if recursion gets too deep, and insertion sort for small partitions. Used by C++ STL.

Implementation

      
 function introSort(arr) {
  const maxDepth = Math.floor(2 * Math.log2(arr.length));
  function rec(lo, hi, depth) {
    if (hi - lo < 16) { insertionSort(arr, lo, hi); return; }
    if (depth === 0) { heapSort(arr, lo, hi); return; }
    const pivot = medianOfThree(arr, lo, hi);
    const pi = partition(arr, lo, hi, pivot);
    rec(lo, pi - 1, depth - 1);
    rec(pi + 1, hi, depth - 1);
  }
  rec(0, arr.length - 1, maxDepth);
} def intro_sort(arr):
    max_depth = 2 * int(math.log2(len(arr)))
    def rec(lo, hi, depth):
        if hi - lo < 16:
            insertion_sort(arr, lo, hi); return
        if depth == 0:
            heap_sort(arr, lo, hi); return
        pivot = median_of_three(arr, lo, hi)
        pi = partition(arr, lo, hi, pivot)
        rec(lo, pi - 1, depth - 1)
        rec(pi + 1, hi, depth - 1)
    rec(0, len(arr) - 1, max_depth) void introSort(vector<int>& arr) {
  int maxDepth = 2 * (int)log2(arr.size());
  function<void(int,int,int)> rec = [&](int lo, int hi, int d) {
    if (hi - lo < 16) { insertionSort(arr,lo,hi); return; }
    if (d == 0) { make_heap(&arr[lo],&arr[hi+1]);
                  sort_heap(&arr[lo],&arr[hi+1]); return; }
    int pivot = medianOfThree(arr,lo,hi);
    int pi = partition(arr,lo,hi,pivot);
    rec(lo, pi-1, d-1);
    rec(pi+1, hi, d-1);
  };
  rec(0, arr.size()-1, maxDepth);
} void IntroSort(int[] arr) {
  int maxDepth = 2 * (int)Math.Log2(arr.Length);
  void Rec(int lo, int hi, int depth) {
    if (hi - lo < 16) { InsertionSort(arr, lo, hi); return; }
    if (depth == 0) { HeapSort(arr, lo, hi); return; }
    int pivot = MedianOfThree(arr, lo, hi);
    int pi = Partition(arr, lo, hi, pivot);
    Rec(lo, pi - 1, depth - 1);
    Rec(pi + 1, hi, depth - 1);
  }
  Rec(0, arr.Length - 1, maxDepth);
} void introSort(int arr[], int n) {
  int maxDepth = 2 * (int)log2(n);
  void rec(int lo, int hi, int depth) {
    if (hi - lo < 16) { insertionSort(arr,lo,hi); return; }
    if (depth == 0) { heapSort(arr,lo,hi); return; }
    int pivot = medianOfThree(arr,lo,hi);
    int pi = partition(arr,lo,hi,pivot);
    rec(lo, pi-1, depth-1);
    rec(pi+1, hi, depth-1);
  }
  rec(0, n-1, maxDepth);
} 