Intro Sort

Hybrid of quicksort and insertion sort — uses quicksort for large ranges, insertion sort for small ones.

Best: O(n log n) · Avg: O(n log n) · Worst: O(n log n) · Space: O(log n)

22
37
38
89
34
98
32
28
79
70
43
83
98
53
70
Speed5
Size15
TypeScript
function introSort(arr: number[], lo = 0, hi = arr.length - 1, maxDepth = 2 * Math.log2(arr.length)) {
  while (lo < hi) {
    if (hi - lo < 8) {
      insertionSort(arr, lo, hi + 1);
      return;
    }
    if (maxDepth-- <= 0) {
      heapSort(arr, lo, hi + 1);
      return;
    }
    const p = partition(arr, lo, hi);
    introSort(arr, lo, p - 1, maxDepth);
    lo = p + 1;
  }
  return arr;
}
function partition(a: number[], lo: number, hi: number): number {
  let i = lo - 1;
  for (let j = lo; j < hi; j++)
    if (a[j] < a[hi]) [a[++i], a[j]] = [a[j], a[i]];
  [a[++i], a[hi]] = [a[hi], a[i]];
  return i;
}