Introduction to Sorting

Sorting is the most studied problem in computing, and it's not because ordered data is pretty. It's that an enormous number of problems become easy once the input is sorted, and stay hard otherwise.

Finding a duplicate, finding the closest pair, merging two datasets, answering "is this value present" quickly, spotting overlapping bookings: all of these are awkward on unordered data and nearly trivial on sorted data. Most of this section is really about that second effect.

What sorting buys you

The last two rows are the whole of the later pages in this section. The pattern is always the same: sorting costs O(n log n) once, and turns a quadratic question into a linear one.

Watch them run

Worth seeing this before reading any of the theory below. Pick an algorithm and press play, then switch the input to "nearly sorted" and run insertion sort and selection sort in turn. The counters tell the story better than any complexity table does.

The three properties that actually matter

Textbooks lead with time complexity. In practice you choose a sort on three axes, and complexity is only the first one.

Stability

A sort is stable when equal elements come out in the same relative order they went in. With bare numbers this is invisible, since two equal numbers are indistinguishable. It matters the moment you sort records.

Say you have employees sorted by name, and you now sort them by department. With a stable sort, each department's employees stay in name order, and you've effectively sorted by two keys for the price of one. With an unstable sort, that ordering gets destroyed and the second sort has to compare both fields.

Memory

An in-place sort uses O(1) or O(log n) extra memory beyond the array itself. Merge sort doesn't, since it needs a scratch buffer as large as the input, and on a large dataset that's the difference between fitting in memory and not.

Adaptivity

An adaptive sort runs faster on input that's already partly ordered. Insertion sort is strongly adaptive and runs in O(n) on sorted input; selection sort isn't adaptive at all and does the same n²/2 comparisons no matter what you feed it. Real-world data is very often partly ordered, so this is worth more than it looks.

Try it above: run selection sort on "already sorted" and watch the comparison count refuse to drop.

Why nothing beats n log n

Every algorithm on this page except counting sort is a comparison sort: it learns about the input only by asking "is a bigger than b?". That restriction alone forces a lower bound, and the argument is short enough to follow all the way through.

A run of the algorithm is a sequence of yes/no answers. With c comparisons there are at most 2^c distinct answer sequences, so the algorithm can distinguish at most 2^c different inputs. There are n! possible orderings of n distinct values, and the algorithm has to produce a different output for each, so:

2^c  >=  n!
 c   >=  log2(n!)
 c   >=  n log2(n) - n/ln(2)      (Stirling's approximation)
 c   =   Omega(n log n)

So no comparison sort can do better than n log n comparisons in the worst case, and merge sort and heap sort actually achieve it. This is a statement about the problem, not about anyone's cleverness. The comparison sort lower bound has the full derivation via information theory.

Counting sort escapes it by never comparing anything at all, which is covered later in this section.

What real languages actually use

No production sort is a textbook algorithm. Real ones are hybrids, and the hybrid is instructive.

Timsort was written by Tim Peters in 2002 for Python. It's a merge sort that first scans for runs of already-ordered elements, extends short runs using insertion sort, then merges the runs. It's stable, and it's close to O(n) on data that's nearly sorted, which real data often is. It became the default sort in Python, in Java SE 7 for objects, on Android, in V8, and in Swift.

C++'s std::sort typically uses introsort: quick sort, switching to heap sort if the recursion goes too deep (which caps the worst case at O(n log n)), and to insertion sort on small partitions.

The shared lesson is that insertion sort isn't a toy. Every one of these falls back to it for small inputs, because at that size its low constant factor beats an asymptotically better algorithm.

Check yourself

Sources

Sedgewick and Wayne's Algorithms, 4th edition sorting chapter is the standard free reference for this material, with Java implementations and analysis for every algorithm here. Antti Laaksonen's Competitive Programmer's Handbook covers the same ground far more briefly, aimed at people writing code under time pressure.

Bubble, Selection and Insertion Sort

All three of these are O(n²) and all three get taught together, which makes it look like they're the same algorithm with cosmetic differences. They're not. They differ in how many writes they do, whether they notice sorted input, and whether they're stable, and those differences decide which one survives into real code.

Bubble sort

Walk the array comparing neighbors and swapping any that are out of order, and after one pass the largest value has been carried to the end. Repeat.

Its one redeeming feature is the early exit: if a whole pass makes no swaps, the array is sorted and you can stop. That makes it O(n) on already-sorted input. Without that check it's O(n²) unconditionally, and the version without the check is the one most people write.

Switch the input to "already sorted" and watch it stop after a single pass with zero writes.

Selection sort

Find the smallest remaining value, swap it into place, repeat. The comparison count is fixed at n(n-1)/2 no matter what, since it always scans the whole remaining array.

What it does have is the fewest writes of any of these: exactly n-1 swaps, regardless of the input. If comparisons are cheap and writes are expensive, which is the case for flash memory or for records that are large to move, that's a real advantage.

It's not stable, and the reason is worth seeing: swapping a distant minimum into position can jump one of a pair of equal values over the other.

Insertion sort

Grow a sorted prefix. Take the next value, slide it left past everything larger, and drop it in. This is how most people sort a hand of cards.

Notice the holding row underneath. While the shifting loop runs, the value being placed is out of the array entirely, held in a variable, and its old slot has already been overwritten. That's why the bars briefly show a duplicate: it's real, not a rendering artifact.

Insertion sort is stable, adaptive, and in place. On nearly-sorted input each value moves only a step or two, so the inner loop barely runs and the whole thing is close to O(n). That combination is why it's the only one of the three that shows up in production sorts.

Side by side

Run all three on the same input using the full visualizer, and read the table at the bottom. The interesting comparisons are on the non-random presets.

Pick any two and compare the frame counts.

In code

function bubbleSort(a) {
  for (let pass = 0; pass < a.length - 1; pass++) {
    let swapped = false;
    for (let i = 0; i < a.length - 1 - pass; i++) {
      if (a[i] > a[i + 1]) {
        [a[i], a[i + 1]] = [a[i + 1], a[i]];
        swapped = true;
      }
    }
    if (!swapped) break;      // the whole point: sorted input costs one pass
  }
  return a;
}

function selectionSort(a) {
  for (let i = 0; i < a.length - 1; i++) {
    let min = i;
    for (let j = i + 1; j < a.length; j++) if (a[j] < a[min]) min = j;
    if (min !== i) [a[i], a[min]] = [a[min], a[i]];   // exactly one swap per i
  }
  return a;
}

function insertionSort(a) {
  for (let i = 1; i < a.length; i++) {
    const value = a[i];        // held out of the array while we shift
    let j = i - 1;
    while (j >= 0 && a[j] > value) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = value;
  }
  return a;
}

Check yourself

As flowcharts

The same algorithms, drawn as flowcharts, where the dashed copper arrows are loops back to an earlier step. Click any box with a dot to see why that step is there.

Bubble sort as a flowchart.

Selection sort as a flowchart.

Insertion sort as a flowchart.