How Do Computers Sort Things? Trading Comparisons Against Memory

An algorithm that compares every item with every other performs a number of comparisons proportional to the square of the list length, so doubling the list quadruples the work. An algorithm that repeatedly halves the problem performs work proportional to the length multiplied by its logarithm, so doubling the list slightly more than doubles the work. For ten items the difference is negligible and for ten million it is the difference between a fraction of a second and hours. That is why computer science describes algorithms by how their cost grows rather than by how long they take on any particular machine, since hardware speed changes by a constant factor while growth rate changes everything. A proof establishes that any sorting method based on comparing pairs of items must perform at least a number of comparisons proportional to length times logarithm in the worst case, which means the best comparison sorts are not merely good but provably close to optimal.

A handful of algorithms cover almost all practical use and each has a characteristic strength:

• •Bubble and insertion sort, which repeatedly move items into place, are simple, cost grows with the square of the length, and insertion sort is genuinely the fastest option for very short lists and for lists already nearly in order
• •Merge sort, which splits the list in half, sorts each half and merges the results, has guaranteed good performance in all cases and requires extra memory for the merge
• •Quicksort, which picks a pivot, partitions items around it and recurses, is usually the fastest in practice because it works within the existing array with good memory behaviour, and degrades badly if pivots are chosen poorly
• •Heapsort, which builds a structure allowing repeated extraction of the largest item, guarantees good worst-case performance without extra memory
• •Counting and radix sorts, which do not compare items at all but distribute them by digit or value, and therefore beat the comparison limit for suitable data
• •Hybrid algorithms used in real libraries, including Timsort, which exploits runs already in order and is the default in several major languages

Beyond speed, several characteristics determine which algorithm a library actually uses. Stability means that items comparing equal keep their original relative order, which matters whenever a list is sorted by one field and then another, since a stable sort by surname after sorting by first name leaves people with the same surname in first-name order. In-place operation means little extra memory is used, which matters on constrained devices and for very large data. Worst-case behaviour matters where an adversary could supply input, since quicksort's poor case can be triggered deliberately, which has been used as a denial of service attack. Adaptivity, performing better on partly ordered input, is valuable because real data is frequently partly ordered already. Parallelisability matters on multi-core hardware. Real implementations therefore combine approaches, switching to insertion sort for small segments and falling back to a guaranteed method if recursion goes too deep.

Sorting is a prerequisite rather than an end. A sorted list can be searched by repeated halving in time proportional to the logarithm of its length, which is the difference between checking a million records and checking twenty. Databases maintain sorted indexes for exactly that reason, and the tree structures they use are sorting machinery in another form. Finding duplicates, computing the median, detecting the closest pair of points and merging datasets all become easy once sorted and are awkward otherwise. Compression algorithms use sorted transformations of data. Graphics uses sorting by depth to decide what occludes what. External sorting, handling data too large for memory, drove the design of tape and disk systems and remains central to processing datasets at scale. And the study of sorting produced much of the analytical apparatus used for reasoning about algorithms generally, which is why it occupies so much space in every computing curriculum for a task that sounds like tidying.

Sorting methods are judged by how work grows with list length, and the difference between growth proportional to the square and to length times logarithm decides everything at scale. Any comparison-based sort must perform at least length times logarithm comparisons, so the best are provably near optimal. Stability, memory use, worst-case behaviour and performance on partly ordered data decide which is chosen, and real libraries use hybrids. Sorting exists mainly to make searching, deduplication and merging cheap.