Types of Sorting Algorithms

Almost every sorting algorithm belongs to one of these groups, and knowing the group tells you most of what you need before you learn a single line of the algorithm itself.

• Simple comparison sorts — nested loops, O(n²), easy to write and easy to reason about. Bubble, Selection, Insertion, Shell.
• Divide-and-conquer sorts — split the problem, solve the halves, combine. This is where O(n log n) comes from. Merge, Quick, Heap.
• Non-comparison sorts — never compare two elements; use the key itself as an address. This is the only way to beat O(n log n). Counting, Radix, Bucket.
• Hybrids — deliberately switch strategies depending on the data, to get the best case of one and the guarantees of another. Tim Sort, Introsort. These are what production code actually runs.

Notice the arc: the first family is what you write by hand, the second is what the theory is about, the third is the loophole, and the fourth is what ships.

These all work by comparing elements and shuffling them around, using two nested passes over the data. That nesting is exactly why they are O(n²). They are not "bad" algorithms — they are small, need no extra memory, and beat the clever ones on tiny inputs because they have almost no setup cost.

Bubble Sort — repeatedly compares adjacent pairs and swaps them if they are out of order, so on each pass the largest remaining value floats to the end. With an early-exit flag it detects a sorted array in O(n). Genuinely useful only for teaching and for cheap "is this already sorted?" checks.

Selection Sort — scans the unsorted region for the minimum and swaps it into place. Always O(n²) with no early exit, but it performs exactly n−1 swaps regardless of input. That makes it the right choice in the narrow case where writes are far more expensive than reads, such as flash memory with limited write cycles.

Insertion Sort — takes each element and slides it back into its place among the already-sorted prefix, exactly like arranging a hand of playing cards. The most useful of the three by a wide margin: it is stable, it runs in O(n) on nearly-sorted input, and it is so cheap on small arrays that both Tim Sort and Introsort call it internally for sub-arrays below about 32 elements.

Shell Sort — Insertion Sort with a twist: first compare elements far apart, then narrow the gap, so big values travel long distances cheaply before the final near-sorted pass. Depending on the gap sequence it reaches roughly O(n log²n) with O(1) space and no recursion, which is why it still turns up in embedded code.

The insight shared by this family is that sorting two halves and combining them is cheaper than sorting the whole thing at once. Halving repeatedly takes log n steps, each step costs O(n), and O(n log n) is the result.

Merge Sort — splits the array down to single elements, then zips sorted pieces back together. Its guarantee is unusually strong: O(n log n) in the best, average and worst case, and it is stable. The price is O(n) auxiliary memory. Because it reads and writes sequentially, it is also the basis of external sorting for data too big for RAM, and it is the natural choice for linked lists where there is no random access.

Quick Sort — picks a pivot, partitions everything smaller to the left and larger to the right (which places the pivot at its final position), then recurses into both sides. Fastest comparison sort in practice for in-memory arrays, sorts in place, but unstable, and it degrades to O(n²) if the pivot choice is consistently terrible. See pivot selection strategies for how real implementations prevent that.

Heap Sort — rearranges the array into a max-heap (every parent larger than its children), then repeatedly swaps the root to the end and repairs the heap. It is the only common algorithm that gives you O(n log n) worst case and O(1) extra space simultaneously, which makes it the pick for memory-constrained and real-time systems. Its weakness is cache behaviour: it jumps around the array rather than reading it in order.

Every algorithm above learns about the data only by asking "is A before B?". That restriction imposes a hard floor of O(n log n). This family sidesteps it by using the value itself as an array index, which requires the keys to be integers or something that maps cleanly to integers.

Counting Sort — tallies how many times each value occurs, then rebuilds the array straight from the tallies. O(n + k) where k is the size of the value range. Perfect for exam grades (0–100), ages, or byte values; useless for arbitrary 64-bit integers, because k would be astronomically larger than n.

Radix Sort — the fix for Counting Sort's range problem. Sort by the last digit, then the next, and so on, using a stable Counting Sort at each digit. Ten buckets are enough no matter how large the numbers are. This is how mechanical punch-card sorters worked a century ago, and it is why Radix Sort dominates on GPUs today: its memory access pattern parallelises beautifully.

Bucket Sort — spread the values across a set of ranges ("buckets"), sort each small bucket, then concatenate. Excellent when the data is roughly uniformly distributed and awful when it is not: if everything lands in one bucket you have done all the setup work and still have the original problem.

Real standard libraries do not pick one algorithm. They detect what kind of data they were handed and switch.

Tim Sort — written by Tim Peters for Python in 2002 and now the most consequential sorting algorithm in the world. It scans for "runs" of already-ordered elements, extends short runs with Insertion Sort, and merges the runs with a carefully tuned Merge Sort. Because real data is usually partly ordered already, it often approaches O(n) where a textbook sort would do the full O(n log n). It is stable, and it is the default in Python, Java (for objects), Kotlin, Swift and JavaScript engines.

Introsort — what std::sort runs in C++. Start as Quick Sort for its speed; if recursion goes deeper than about 2·log n, conclude the pivots are going badly and switch to Heap Sort to guarantee O(n log n); for partitions below a small threshold, finish with Insertion Sort. Speed most of the time, a safety net for the pathological case.

The lesson generalises well beyond sorting: the strongest engineering answer is usually not the cleverest single algorithm but a cheap check that routes the work to the right one.

If you are starting out, this order wastes the least time:

• Insertion Sort first — it is intuitive, genuinely useful, and introduces stability and adaptivity.
• Merge Sort next — the cleanest introduction to divide and conquer and to reasoning about correctness.
• Quick Sort third — partitioning is a technique you will reuse constantly (quickselect, median finding, three-way partitioning).
• Heap Sort fourth, mainly because heaps themselves are worth knowing for priority queues.
• Counting or Radix Sort fifth, to break the assumption that comparison is the only way to sort.
• Tim Sort last, as the synthesis — it will make more sense once Merge and Insertion Sort are familiar.

Read each deep dive, then run the same algorithm in the visualiser at the slowest speed and narrate what it is doing out loud. The narration is what converts reading into understanding.