AlgoScope

More Sorts

Each of these sorts exists because a classic has a weak spot. Insertion sort moves values one slot at a time, so shell sort moves them in strides first and finishes with a gap of one on a nearly sorted array. Quicksort chokes on duplicates, so three-way partitioning gathers every copy of the pivot into a middle zone that is final after one pass. Comparison sorts cannot beat n log n, so bucket sort uses the values themselves to scatter them into ranges and sorts each small bucket. Merge sort ignores order that is already there, so timsort finds the ascending runs in the data, extends short ones with insertion sort, and merges runs instead of single elements. Introsort is what std::sort actually runs: quicksort, but a range of four or fewer values goes to insertion sort, and any stretch that has been partitioned 2 log n times without finishing is handed to heap sort, so bad pivots can slow it down but never make it quadratic. Randomized quicksort takes the other route to a guarantee: choose the pivot at random, and no input can be arranged to be slow on every run. The result compares the same input under thirty seeds, which is what expected running time means: an average over the algorithm's own coin flips, not over inputs.

The player

Randomized quicksort on 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 with seed 7.range 0-1110213243546576879810911101211

Quicksort, but the pivot is chosen at random from the range instead of always being the last value. With the last value as pivot, this exact input recurses 11 deep, the worst case, one level per value. A random pivot does not make any input impossible, it makes no input reliably bad: whoever wrote the input cannot know which value will be the pivot. Seed 7 decides the rolls here. Change it and the same input takes a different path.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 6, with their answers.

  1. The pivot is 8. Where does it land once the range is partitioned?

    • Index 0
    • Index 7
    • Index 11

    Answer: Index 7. It lands at lo plus the number of other values at most 8: index 7. A pivot near the middle of the values splits the range evenly, and a random pick is near the middle far more often than it is at an end.

  2. The pivot is 6. Where does it land once the range is partitioned?

    • Index 0
    • Index 5
    • Index 6

    Answer: Index 5. It lands at lo plus the number of other values at most 6: index 5. A pivot near the middle of the values splits the range evenly, and a random pick is near the middle far more often than it is at an end.

  3. The pivot is 4. Where does it land once the range is partitioned?

    • Index 0
    • Index 3
    • Index 4

    Answer: Index 3. It lands at lo plus the number of other values at most 4: index 3. A pivot near the middle of the values splits the range evenly, and a random pick is near the middle far more often than it is at an end.

  4. The pivot is 2. Where does it land once the range is partitioned?

    • Index 0
    • Index 1
    • Index 2

    Answer: Index 1. It lands at lo plus the number of other values at most 2: index 1. A pivot near the middle of the values splits the range evenly, and a random pick is near the middle far more often than it is at an end.

  5. The pivot is 10. Where does it land once the range is partitioned?

    • Index 8
    • Index 9
    • Index 11

    Answer: Index 9. It lands at lo plus the number of other values at most 10: index 9. A pivot near the middle of the values splits the range evenly, and a random pick is near the middle far more often than it is at an end.

  6. The pivot is 11. Where does it land once the range is partitioned?

    • Index 10
    • Index 11

    Answer: Index 10. It lands at lo plus the number of other values at most 11: index 10. A pivot near the middle of the values splits the range evenly, and a random pick is near the middle far more often than it is at an end.

How it runs, step by step

  1. Quicksort, but the pivot is chosen at random from the range instead of always being the last value. With the last value as pivot, this exact input recurses 11 deep, the worst case, one level per value. A random pivot does not make any input impossible, it makes no input reliably bad: whoever wrote the input cannot know which value will be the pivot. Seed 7 decides the rolls here. Change it and the same input takes a different path.

    Randomized quicksort on 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 with seed 7.

  2. Indices 0 to 11, depth 0. The seed picks index 7, holding 8, as the pivot, and it is swapped to the end so the ordinary partition can run.

    Pivot 8 chosen at random from 0 to 11.

  3. 1 is at most 8: it belongs on the left, so it moves to index 0.

    1 moves to index 0.

  4. 2 is at most 8: it belongs on the left, so it moves to index 1.

    2 moves to index 1.

  5. 3 is at most 8: it belongs on the left, so it moves to index 2.

    3 moves to index 2.

  6. 4 is at most 8: it belongs on the left, so it moves to index 3.

    4 moves to index 3.

  7. 5 is at most 8: it belongs on the left, so it moves to index 4.

    5 moves to index 4.

  8. 6 is at most 8: it belongs on the left, so it moves to index 5.

    6 moves to index 5.

  9. 7 is at most 8: it belongs on the left, so it moves to index 6.

    7 moves to index 6.

  10. 12 is above 8: leave it.

    12 stays.

  11. 9 is above 8: leave it.

    9 stays.

  12. 10 is above 8: leave it.

    10 stays.

  13. 11 is above 8: leave it.

    11 stays.

  14. The pivot 8 lands at index 7: 7 on its left, 4 on its right. A reasonable split, which is what random pivots deliver most of the time.

    8 placed at index 7.

  15. Indices 0 to 6, depth 1. The seed picks index 5, holding 6, as the pivot, and it is swapped to the end so the ordinary partition can run.

    Pivot 6 chosen at random from 0 to 6.

  16. 1 is at most 6: it belongs on the left, so it moves to index 0.

    1 moves to index 0.

  17. 2 is at most 6: it belongs on the left, so it moves to index 1.

    2 moves to index 1.

  18. 3 is at most 6: it belongs on the left, so it moves to index 2.

    3 moves to index 2.

  19. 4 is at most 6: it belongs on the left, so it moves to index 3.

    4 moves to index 3.

  20. 5 is at most 6: it belongs on the left, so it moves to index 4.

    5 moves to index 4.

  21. 7 is above 6: leave it.

    7 stays.

  22. The pivot 6 lands at index 5: 5 on its left, 1 on its right. A reasonable split, which is what random pivots deliver most of the time.

    6 placed at index 5.

  23. Indices 0 to 4, depth 2. The seed picks index 3, holding 4, as the pivot, and it is swapped to the end so the ordinary partition can run.

    Pivot 4 chosen at random from 0 to 4.

  24. 1 is at most 4: it belongs on the left, so it moves to index 0.

    1 moves to index 0.

  25. 2 is at most 4: it belongs on the left, so it moves to index 1.

    2 moves to index 1.

  26. 3 is at most 4: it belongs on the left, so it moves to index 2.

    3 moves to index 2.

  27. 5 is above 4: leave it.

    5 stays.

  28. The pivot 4 lands at index 3: 3 on its left, 1 on its right. A reasonable split, which is what random pivots deliver most of the time.

    4 placed at index 3.

  29. Indices 0 to 2, depth 3. The seed picks index 1, holding 2, as the pivot, and it is swapped to the end so the ordinary partition can run.

    Pivot 2 chosen at random from 0 to 2.

  30. 1 is at most 2: it belongs on the left, so it moves to index 0.

    1 moves to index 0.

  31. 3 is above 2: leave it.

    3 stays.

  32. The pivot 2 lands at index 1: 1 on its left, 1 on its right. A reasonable split, which is what random pivots deliver most of the time.

    2 placed at index 1.

  33. Indices 8 to 11, depth 1. The seed picks index 9, holding 10, as the pivot, and it is swapped to the end so the ordinary partition can run.

    Pivot 10 chosen at random from 8 to 11.

  34. 9 is at most 10: it belongs on the left, so it moves to index 8.

    9 moves to index 8.

  35. 12 is above 10: leave it.

    12 stays.

  36. 11 is above 10: leave it.

    11 stays.

  37. The pivot 10 lands at index 9: 1 on its left, 2 on its right. A reasonable split, which is what random pivots deliver most of the time.

    10 placed at index 9.

  38. Indices 10 to 11, depth 2. The seed picks index 10, holding 11, as the pivot, and it is swapped to the end so the ordinary partition can run.

    Pivot 11 chosen at random from 10 to 11.

  39. 12 is above 11: leave it.

    12 stays.

  40. The pivot 11 lands at index 10: 0 on its left, 1 on its right. A lopsided split, which a random pivot cannot rule out, only make rare.

    11 placed at index 10.

  41. Sorted with 27 comparisons and 12 swaps, recursing 4 deep. The last-value pivot needs 11 on this input. Run the same input under 30 other seeds and the depth ranges from 4 to 8, averaging 5.2. That average over the algorithm's own coin flips, for a fixed input, is the expected running time. It is not the same as averaging over inputs: here the input is as bad as it gets and the expectation is still O(n log n), because the only way to be slow is a run of unlucky rolls, and that run is rare on every input, not just on typical ones.

    Sorted after 27 comparisons. Depth 4 against 11 deterministic.

The code

More Sorts, in Python

def shell_sort(a):
    gap = len(a) // 2
    while gap > 0:                                          # insertion sort with a stride, halving to 1
        for i in range(gap, len(a)):
            j = i
            while j >= gap and a[j - gap] > a[j]:
                swap(a, j - gap, j); j -= gap
        gap //= 2

def quick_sort3(a, lo, hi):                                 # Dijkstra's three-way partition
    if lo >= hi: return
    pivot = a[lo]
    lt = lo; i = lo + 1; gt = hi
    while i <= gt:
        if a[i] < pivot:                                    # grow the < zone
            swap(a, lt, i); lt += 1; i += 1
        elif a[i] > pivot:                                  # grow the > zone; look at the new a[i] next
            swap(a, i, gt); gt -= 1
        else:                                               # equal: it stays in the middle
            i += 1
    quick_sort3(a, lo, lt - 1); quick_sort3(a, gt + 1, hi)  # the equal zone is never touched again

def bucket_sort(a, buckets):
    bucket = [[] for _ in range(buckets)]
    for v in a: bucket[v * buckets // 100].append(v)        # scatter: the value range split evenly
    for b in bucket: b.sort()                               # each bucket is small: insertion sort
    k = 0
    for b in bucket:                                        # gather in bucket order
        for v in b: a[k] = v; k += 1

def tim_sort(a, min_run):
    runs = []
    i = 0
    while i < len(a):
        end = i + 1
        while end < len(a) and a[end - 1] <= a[end]:        # a natural ascending run
            end += 1
        end = max(end, min(i + min_run, len(a)))            # too short: extend it
        insertion_sort(a, i, end - 1); runs.append(range(i, end))
        i = end
    while len(runs) > 1: runs = merge_neighbours(a, runs)   # bottom-up merges, like merge sort

def intro_sort(a):
    sort(a, 0, len(a) - 1, 2 * log2(len(a)))                # the depth budget
def sort(a, lo, hi, depth):
    if hi - lo + 1 <= SMALL:                                # tiny range: insertion sort wins
        insertion_sort(a, lo, hi); return
    if depth == 0:                                          # budget spent: quicksort is degrading
        heap_sort(a, lo, hi); return
    p = partition(a, lo, hi)                                # Lomuto, last value as pivot
    sort(a, lo, p - 1, depth - 1); sort(a, p + 1, hi, depth - 1)

def randomized_quick_sort(a, lo, hi, rng):
    if lo >= hi: return
    swap(a, rng.randint(lo, hi), hi)             # a random pivot moves to the end
    p = partition(a, lo, hi)                     # then the usual Lomuto partition
    randomized_quick_sort(a, lo, p - 1, rng); randomized_quick_sort(a, p + 1, hi, rng)
    # expected depth O(log n) on every input

More Sorts, in JavaScript

function shellSort(a) {
  let gap = Math.floor(a.length / 2);
  while (gap > 0) {                                       // insertion sort with a stride, halving to 1
    for (let i = gap; i < a.length; i++) {
      let j = i;
      while (j >= gap && a[j - gap] > a[j]) { swap(a, j - gap, j); j -= gap; }
    }
    gap = Math.floor(gap / 2);
  }
}

function quickSort3(a, lo, hi) {                          // Dijkstra's three-way partition
  if (lo >= hi) return;
  const pivot = a[lo];
  let lt = lo;
  let i = lo + 1;
  let gt = hi;
  while (i <= gt) {
    if (a[i] < pivot) swap(a, lt++, i++);                 // grow the < zone
    else if (a[i] > pivot) swap(a, i, gt--);              // grow the > zone; look at the new a[i] next
    else i++;                                             // equal: it stays in the middle
  }
  quickSort3(a, lo, lt - 1); quickSort3(a, gt + 1, hi);   // the equal zone is never touched again
}

function bucketSort(a, buckets) {
  const bucket = Array.from({ length: buckets }, () => []);
  for (const v of a) bucket[Math.floor((v * buckets) / 100)].push(v);   // scatter: the value range split evenly
  for (const b of bucket) b.sort((x, y) => x - y);                      // each bucket is small: insertion sort
  let k = 0;
  for (const b of bucket) for (const v of b) a[k++] = v;                // gather in bucket order
}

function timSort(a, minRun) {
  let runs = [];
  let i = 0;
  while (i < a.length) {
    let end = i + 1;
    while (end < a.length && a[end - 1] <= a[end]) end++;   // a natural ascending run
    end = Math.max(end, Math.min(i + minRun, a.length));    // too short: extend it
    insertionSort(a, i, end - 1); runs.push([i, end]);
    i = end;
  }
  while (runs.length > 1) runs = mergeNeighbours(a, runs);  // bottom-up merges, like merge sort
}

const introSort = (a) => sort(a, 0, a.length - 1, 2 * log2(a.length));  // the depth budget
function sort(a, lo, hi, depth) {
  if (hi - lo + 1 <= SMALL) { insertionSort(a, lo, hi); return; }       // tiny range: insertion sort wins
  if (depth === 0) { heapSort(a, lo, hi); return; }                     // budget spent: quicksort is degrading
  const p = partition(a, lo, hi);                                       // Lomuto, last value as pivot
  sort(a, lo, p - 1, depth - 1); sort(a, p + 1, hi, depth - 1);
}

function randomizedQuickSort(a, lo, hi, rng) {
  if (lo >= hi) return;
  swap(a, rng.nextInt(lo, hi + 1), hi);           // a random pivot moves to the end
  const p = partition(a, lo, hi);                 // then the usual Lomuto partition
  randomizedQuickSort(a, lo, p - 1, rng); randomizedQuickSort(a, p + 1, hi, rng);
}                                                 // expected depth O(log n) on every input

More Sorts, in Kotlin

fun shellSort(a: IntArray) {
    var gap = a.size / 2
    while (gap > 0) {                                        // insertion sort with a stride, halving to 1
        for (i in gap until a.size) {
            var j = i
            while (j >= gap && a[j - gap] > a[j]) { swap(a, j - gap, j); j -= gap }
        }
        gap /= 2
    }
}

fun quickSort3(a: IntArray, lo: Int, hi: Int) {             // Dijkstra's three-way partition
    if (lo >= hi) return
    val pivot = a[lo]
    var lt = lo; var i = lo + 1; var gt = hi
    while (i <= gt) {
        when {
            a[i] < pivot -> swap(a, lt++, i++)                 // grow the < zone
            a[i] > pivot -> swap(a, i, gt--)                   // grow the > zone; look at the new a[i] next
            else -> i++                                        // equal: it stays in the middle
        }
    }
    quickSort3(a, lo, lt - 1); quickSort3(a, gt + 1, hi)     // the equal zone is never touched again
}

fun bucketSort(a: IntArray, buckets: Int) {
    val bucket = List(buckets) { mutableListOf<Int>() }
    for (v in a) bucket[v * buckets / 100] += v               // scatter: the value range split evenly
    for (b in bucket) b.sort()                                // each bucket is small: insertion sort
    var k = 0
    for (b in bucket) for (v in b) a[k++] = v                 // gather in bucket order
}

fun timSort(a: IntArray, minRun: Int) {
    var runs = mutableListOf<IntRange>()
    var i = 0
    while (i < a.size) {
        var end = i + 1
        while (end < a.size && a[end - 1] <= a[end]) end++    // a natural ascending run
        end = max(end, min(i + minRun, a.size))              // too short: extend it
        insertionSort(a, i, end - 1); runs += i until end
        i = end
    }
    while (runs.size > 1) runs = mergeNeighbours(a, runs)    // bottom-up merges, like merge sort
}

fun introSort(a: IntArray) = sort(a, 0, a.size - 1, 2 * log2(a.size))   // the depth budget
fun sort(a: IntArray, lo: Int, hi: Int, depth: Int) {
    if (hi - lo + 1 <= SMALL) { insertionSort(a, lo, hi); return }   // tiny range: insertion sort wins
    if (depth == 0) { heapSort(a, lo, hi); return }                   // budget spent: quicksort is degrading
    val p = partition(a, lo, hi)                                      // Lomuto, last value as pivot
    sort(a, lo, p - 1, depth - 1); sort(a, p + 1, hi, depth - 1)
}

fun randomizedQuickSort(a: IntArray, lo: Int, hi: Int, rng: Random) {
    if (lo >= hi) return
    swap(a, rng.nextInt(lo, hi + 1), hi)             // a random pivot moves to the end
    val p = partition(a, lo, hi)                     // then the usual Lomuto partition
    randomizedQuickSort(a, lo, p - 1, rng); randomizedQuickSort(a, p + 1, hi, rng)
}                                                    // expected depth O(log n) on every input

Write it yourself

Define threeWayQuickSort(values) and return the same values in ascending order. It runs in your browser against this lesson's own 2 examples.

// Partition into less than, equal to and greater than the pivot, so runs of duplicates are finished in one pass.function threeWayQuickSort(values) { return values;}
6 linesTab indents. Escape, then Tab, leaves the editor. Ctrl-Enter runs (Cmd-Enter on a Mac).

    Remember

    • Shell sort: insertion sort with gaps n/2, n/4, ..., 1. The big gaps move values far cheaply.
    • Three-way quicksort: zones smaller, equal, larger. The equal zone is final, so duplicates cost O(n).
    • Bucket sort is linear on evenly spread data. Timsort merges natural runs, O(n) on sorted input. Introsort is quicksort with insertion sort under 5 values and heap sort once 2 log n partitions have not finished.

    Where this is used

    std::sort is introsortStandard libraries

    Since C++11 the standard has required O(n log n) worst case from std::sort, which plain quicksort cannot promise, and libstdc++ meets it with introsort. Its constants are worth seeing next to the visualization: median-of-three pivots rather than a fixed position, the heap sort fallback at depth 2 log2 n, and a threshold of 16 rather than 4, below which it does not recurse at all - it leaves those stretches alone and cleans the whole array up with one insertion sort pass at the end, which is cheaper than many small ones. Quicksort stays the main engine because it partitions in place and walks memory sequentially. Heap sort is reached only on input that was already defeating it.

    Timsort in JavaScript enginesLanguage runtimes

    V8 replaced its quicksort for Array.prototype.sort with Timsort in V8 7.0 and Chrome 70, in 2018, and ES2019 then made stability part of the language, which a quicksort cannot provide: sorting a table by one column and then by another has to leave the first order intact inside ties. Run detection is the second payoff, because web data rarely arrives shuffled - arrays built by appending, filtered out of an already sorted list, or re-sorted after a single edit are mostly ordered already, and those are the shapes V8's own benchmarks improved on most.

    Range partitioning in distributed sortsData

    Spark's RangePartitioner and Hadoop's TeraSort sort a dataset larger than one machine by choosing boundary keys, shipping each record to the partition whose range covers it, and sorting each partition locally. That is bucket sort with the scatter step turned into a network shuffle, and the payoff is the same: because the buckets are ordered, concatenating the results needs no final merge across machines. The boundaries come from sampling the data rather than cutting the key range into equal slices, since even spread is the one assumption real input does not honour.

    Random pivots as a denial-of-service defenceSecurity

    A deterministic quicksort picks its pivot by a fixed rule, so anyone who knows the rule can construct the input that drives it quadratic. McIlroy showed in 1999 that an adversarial comparison function can do this to such an implementation without even knowing the values being sorted. A sort behind a public endpoint then becomes a way to burn CPU with a small request. Drawing the pivot from a random source forces the attacker to guess the seed instead, which is why production sorts either randomise or, like introsort, cap the damage with a depth limit.

    Why it works this way

    Why halving the gap is the worst of the common gap sequences

    The last pass of shell sort is a plain insertion sort, so the result is correct whatever gaps came before. The earlier passes exist only to remove distant inversions cheaply so that final pass has almost nothing left to move. That is also why the halving sequence is a poor choice: when n is a power of two every gap except the last is even, so a value at an odd index is never compared with one at an even index until the gap reaches 1, and the worst case stays quadratic. Hibbard's 2^k - 1 removes that by making the gaps odd and gets Theta(n^1.5). Ciura's 1, 4, 10, 23, 57, 132, 301, 701 is the fastest known in practice and was found by search rather than proof. No optimal sequence is known.

    In the three-way partition, why i does not move when a[i] > pivot

    The value swapped in from position gt arrived from the unexamined right end, so the loop has to look at it on the next turn. That is why the greater branch moves gt and leaves i alone. The less branch can advance both counters because a[lt] is either the pivot itself or a value already known to equal it, so that swap places a known value rather than skipping an unknown one. Advancing i in the greater branch is the standard bug here, and it is quiet: unexamined values end up inside the equal zone, which the recursion never visits again.

    Timsort's run stack is the correctness argument, not bookkeeping

    Timsort does not merge a run as soon as it finds one. It pushes run lengths on a stack and merges only while the top entries break the invariants X > Y + Z and Y > Z, which keep merges roughly balanced and so bound both the total merge cost and how deep the stack can get - which is why the stack can be a small fixed-size array. A 2015 attempt to verify java.util.TimSort formally found the collapse check did not actually restore that invariant, and OpenJDK issue JDK-8072909 is the resulting crash: an array of about 67 million elements overruns the stack and throws ArrayIndexOutOfBoundsException. OpenJDK both enlarged the stack, to 49 entries from 119151 elements up, and tightened mergeCollapse to test four runs rather than three. CPython repaired its own check and then in 3.11 dropped this rule entirely for the powersort merge policy, which chooses the merge order from the run lengths and is provably near-optimal, so listsort.txt now describes powersort rather than the invariants above.

    Why introsort falls back to heap sort rather than merge sort

    Merge sort would cap the worst case just as well, but it needs a buffer, and std::sort is expected to sort in place without allocating. Heap sort is the common O(n log n) sort that runs in O(1) extra space, and its weakness - jumping around memory, so poor cache behaviour - barely matters because it only ever runs on the stretches where quicksort was already failing. The depth budget is loose for the same reason: a healthy quicksort recursion is about log2 n deep, so 2 log2 n almost never fires on ordinary input and the guarantee is effectively free.

    Read more

    Next up

    Skip List

    Layered linked lists where higher levels skip ahead, giving expected O(log n) search.

    Next lesson: Skip List