Why Sorting Matters

Sorting is one of the most studied problems in computer science. It is also one of the most practical: databases sort to enable fast lookups, operating systems sort to schedule processes, and compilers sort to resolve dependencies. The problem is simple—put a list of numbers in order—but the strategies for doing so reveal deep differences in algorithmic thinking. Some algorithms compare neighbors; others divide and conquer; others exploit the structure of the data.

Select an algorithm, adjust the array size, and press Sort. Watch how different algorithms access and rearrange the data. The red bars are being compared; blue bars are being written; green bars are in their final position.

The Algorithms

Bubble Sort is the simplest. Walk through the array, compare each pair of adjacent elements, swap them if they are out of order. Repeat until no swaps occur. It is $O(n^2)$ in the average and worst case, making it useless for large datasets. But it is easy to understand, easy to implement, and surprisingly fast on nearly-sorted data ($O(n)$ best case).

Selection Sort finds the minimum element, puts it at position 0, then finds the next minimum, puts it at position 1, and so on. Always $O(n^2)$ regardless of input. It makes the minimum number of swaps (exactly $n-1$), which matters on hardware where writes are expensive.

Insertion Sort builds a sorted portion one element at a time. Take the next unsorted element and insert it into the correct position among the already-sorted elements, shifting others to make room. $O(n^2)$ worst case, but $O(n)$ on nearly-sorted input. In practice, it is the fastest algorithm for small arrays ($n < 20$), which is why most real-world sorting libraries use it as a subroutine.

Merge Sort divides the array in half, recursively sorts each half, then merges the two sorted halves. It is $O(n \log n)$ in all cases—guaranteed. The cost is $O(n)$ extra memory for the merge step. Watch it: you can see the recursive subdivision, then the merge steps building up larger and larger sorted runs.

Quick Sort picks a pivot element, partitions the array so everything smaller is on the left and everything larger is on the right, then recursively sorts each side. $O(n \log n)$ average, $O(n^2)$ worst case (when the pivot is always the smallest or largest element). In practice, with a good pivot strategy, it is the fastest comparison sort for most data. Most standard library sort functions are variants of quicksort.

Heap Sort builds a max-heap from the array ($O(n)$), then repeatedly extracts the maximum element and places it at the end. $O(n \log n)$ guaranteed, in-place, but not stable. Watch the heap-building phase, then the extraction phase.

Shell Sort is an optimized insertion sort that allows exchanges of elements that are far apart. It starts with a large gap and reduces it. The gap sequence determines the performance. With the Knuth sequence (used here), it achieves roughly $O(n^{3/2})$ in practice.

Radix Sort (LSD) does not compare elements at all. It sorts by individual digits, from least significant to most significant. It is $O(nk)$ where $k$ is the number of digits, making it faster than comparison sorts when $k$ is small. Watch how it groups elements by digit value in each pass.

What to Try

• Bubble sort on reversed data at size 100+. Watch the largest elements "bubble up" one step at a time. This is $O(n^2)$ in its full glory.
• Insertion sort on nearly-sorted data. It finishes almost instantly. This is its $O(n)$ best case.
• Merge sort vs. Quick sort on random data. Merge sort has a visible recursive structure; quick sort's partition step is visually distinct.
• Heap sort. The heap-building phase is distinctive: watch the array become a heap, then the sorted region grows from the right.
• Radix sort on 200+ elements. It does not compare at all. Each pass is a stable bucket sort on one digit.
• Increase array size to 300 and compare $O(n^2)$ algorithms (bubble, selection, insertion) against $O(n \log n)$ algorithms (merge, quick, heap). The speed difference becomes visceral.