Stability, in-place and comparison of sorts

Why it exists

There is no single best sorting algorithm. Choosing one means asking: how much extra memory is allowed, must equal keys keep their order, is the worst case allowed to be slow, is the input nearly sorted, are the keys small integers? GATE asks these questions in tables: "which of the following is stable?", "which is in place?", "which has the best worst-case time?". This page collects the answers in one place and shows why each is true, so that they can be re-derived instead of memorised.

Prerequisites

You need the three elementary sorts (bubble, selection and insertion sort). The other sorts in the table are proved on their own pages (merge, quick, heap, counting and radix); here only their properties are compared.

Precise definitions

Stable. A sort is stable if, whenever $i < j$ and $a_i = a_j$ (equal keys), the record that started at $i$ also comes before the record that started at $j$ in the output. For records that carry extra data this means: ties are broken by the original order.

In place. The sort uses $O(1)$ extra memory besides the input array. (Some texts allow $O(\log n)$ for the recursion stack; GATE usually calls quicksort "in place" and merge sort on arrays "not in place".)

Adaptive. The running time improves when the input is partly sorted (for example insertion sort runs in $\Theta(n + I)$, $I$ the number of inversions).

Online. The sort can accept the keys one at a time and keep the keys seen so far sorted (insertion sort).

Comparison sort. Only uses comparisons between keys, and therefore needs $\Omega(n \log n)$ comparisons in the worst case (lower bound). Counting sort and radix sort use the values of the keys and are not comparison sorts.

Internal and external. An internal sort keeps all data in main memory. An external sort handles data that does not fit, and merge sort is its basis because it reads its input sequentially.

How it works

Where stability comes from. A sort is stable when nothing it does can jump a key over an equal one.

• Insertion sort shifts a key past only the keys that are strictly larger (a[j] > key). The key stops right after an equal key. With >= it would jump over equal keys and become unstable.
• Bubble sort swaps only when a[j] > a[j + 1], never equal neighbours, so equal keys never pass each other.
• Merge sort takes from the left half when the two front keys are equal (the code writes the right key only if it is strictly smaller). This is the whole reason it is stable.
• Counting sort places the keys into the output by scanning the input backwards and decreasing the counters, so the last equal key goes to the last free slot.
• Selection sort swaps the minimum with the first unsorted position, a jump over everything in between. Sorting $2_a, 2_b, 1$ gives $1, 2_b, 2_a$. (A version that shifts the elements between instead of swapping is stable, at the cost of $\Theta(n)$ moves per pass.)
• Quicksort (array partition) swaps keys across the pivot, over equal keys. Heap sort exchanges the root with the last leaf, then sifts down: also long jumps. Neither is stable.

The table below was produced by running real C implementations of all seven sorts, once on a small set of records $2_a\ 3_b\ 2_c\ 1_d\ 3_e\ 1_f$ and then on every array of up to $7$ records with keys from $\{0, 1, 2\}$ ($3279$ arrays per sort), and counting the arrays in which two equal keys came out in a different order. A sort is stable only if that number is zero (and then the argument above proves it for all inputs; a test alone would not). The records show the key, then a letter that marks the original position.

All the properties side by side. The time and space columns are the standard results proved on the pages of the individual sorts; the stable column is the measured one above.

Some remarks that the table cannot fit:

• Quicksort's space. The partition is in place, but the recursion needs a stack: $O(\log n)$ on average, and $O(\log n)$ even in the worst case if the recursive call is made on the smaller part first; otherwise $\Theta(n)$ in the worst case.
• Merge sort. On an array it needs a second array of $\Theta(n)$ keys. On a linked list it can be done with $O(1)$ extra list nodes (and $O(\log n)$ stack) and is still stable.
• Heap sort is the only comparison sort in the table that is both in place and $\Theta(n \log n)$ in the worst case. Its drawbacks are that it is not stable and has poor cache behaviour. (If all keys are equal the sift-downs stop at once and the time is linear; the usual statement for GATE is $\Theta(n \log n)$ in all cases.)
• Counting sort needs the keys to be integers in a range $0, \ldots, k$, time $\Theta(n + k)$, extra space $\Theta(n + k)$; it is stable and not comparison based, so the $n \log n$ bound does not apply to it.
• Swaps and writes. Selection sort moves at most $n - 1$ records, the fewest; merge sort copies $\Theta(n \log n)$ records; insertion and bubble sort move $\Theta(I)$ records.

Why stability matters.

1. Sorting by several keys. To sort employees by department and, inside each department, by name: sort by name first, then sort by department with a stable sort. The department sort leaves the names inside each department in the order the first sort gave them. With an unstable sort the names inside a department come out in arbitrary order.
2. Radix sort sorts by the least significant digit first and then by each more significant digit; it is correct only if every digit pass is stable.
3. Any sort can be made stable by adding the original index as a tiebreaker (compare $(key, index)$ pairs), at the price of $\Theta(n)$ extra memory for the indices.

Choosing a sort.

• Guaranteed $\Theta(n \log n)$ and stable: merge sort. Costs extra space.
• Guaranteed $\Theta(n \log n)$ and $O(1)$ space: heap sort. Not stable.
• Fastest on average in practice: quicksort (with a good pivot rule). Worst case $\Theta(n^2)$, not stable.
• Small or nearly sorted input, or data arriving online: insertion sort.
• Integer keys in a small range: counting sort (or radix sort for larger ranges).
• Expensive record moves: selection sort (fewest moves), or sort pointers to the records.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The elementary sorts of this table are in bubble, selection and insertion sort. The fast ones are developed in merge sort, quicksort and heap sort, and the linear-time non-comparison sorts and the $\Omega(n \log n)$ bound in lower bound and linear-time sorts.

PYQs

Assume that the algorithms considered here sort the
input sequences in ascending order. If the input is
already in ascending order, which of the following are
TRUE?
I. Quick sort runs in Θ(n2) time
II. Bubble sort runs in Θ(n2) time
III. Merge sort runs in Θ(n) time
IV. Insertion sort runs in Θ(n) time

Self-check

Revision card

References