Sorting, from swaps to strategy

01 · Foundation

Comparison-based vs. non-comparison-based

Bubble, Insertion, Selection, Merge, Quick, and Heap Sort all share one trait: the only thing they're allowed to do to figure out order is compare two elements and decide which comes first. That restriction has a hard consequence — no comparison-based sort can ever guarantee better than O(n log n) in the worst case, no matter how cleverly it's written.

Here's the intuitive version of why, without a formal proof. An array of n distinct elements has n! possible orderings, and exactly one of them is "sorted." Every comparison you make gives you at best one bit of information — it splits the remaining possibilities roughly in half. So the number of comparisons needed to narrow n! possibilities down to the one correct answer is at least log₂(n!), and log₂(n!) ≈ n log n. You simply cannot ask fewer yes/no questions than that and still be guaranteed a correct answer for every possible input.

02 · Strategies

Four families you'll keep re-deriving

Nearly every sorting algorithm you'll ever meet is a variation on one of these four underlying strategies. Learn the family, and the specific algorithm becomes a detail.

1. 1 Incremental / comparison-swapBubble, Insertion, and Selection Sort all repeatedly find or fix one element at a time relative to its neighbors. All three are O(n²) and simple to write, but too slow for large inputs. The one exception worth remembering: Insertion Sort is genuinely fast — close to O(n) — on data that's already nearly sorted, since each new element only has to shift a short distance.
2. 2 Divide & conquerMerge Sort and Quick Sort both split the problem, solve the pieces, and combine. They put the work in opposite places: Merge Sort's split is trivial (just cut the array in half) but its merge step does all the work — that guarantees O(n log n) every time, at the cost of O(n) extra space. Quick Sort's partition step does all the work and the combine is trivial (the two sides are already on the correct sides of the pivot) — that's O(n log n) on average and in-place, but a poor pivot choice can degrade it to O(n²).
3. 3 Heap-basedHeap Sort builds a max-heap out of the array, then repeatedly pulls the maximum off the top and moves it to the end. It guarantees O(n log n) like Merge Sort, but does it in-place like Quick Sort — the catch is it isn't stable, and it tends to have worse real-world cache behavior than either.
4. 4 Distribution-basedCounting Sort and Radix Sort skip comparisons altogether and bucket elements by their actual value or by individual digits. This is the non-comparison family from the section above — extremely fast when the value range or digit count is small and known, and a poor fit otherwise.

03 · Worked example

Partitioning in Quick Sort, one pointer at a time

Quick Sort's entire personality comes from one step: partition. Given an array and a chosen pivot, partition rearranges the array so every element smaller than the pivot ends up to its left, everything larger ends up to its right, and the pivot itself lands exactly at the boundary — its final, correct, sorted position. Then Quick Sort recurses on the left and right pieces the same way. That recursive "partition, then repeat on each half" structure is the divide-and-conquer.

Let's trace it on [5, 3, 8, 4, 2] using the Lomuto scheme, with the pivot fixed as the last element — here, 2. We walk a pointer j across every element before the pivot. We also track i, which marks the boundary of "elements confirmed ≤ pivot so far" (it starts at -1, meaning nothing confirmed yet). Whenever arr[j] ≤ pivot, we advance i and swap arr[i] with arr[j] to pull that element into the confirmed region.

Every single element in this array happens to be bigger than the pivot, so i never advances during the scan — nothing gets pulled into the "confirmed small" region. The last step is the one that always runs regardless: swap arr[i + 1] with the pivot at arr[high]. Here that's index 0 swapping with index 4, which drops the pivot straight to the front. After this single partition call, 2 is permanently in its correct sorted position — it will never move again — and Quick Sort now recurses independently on the empty left side and the unsorted right side [3, 8, 4, 5], partitioning each the same way until everything is sorted.

04 · Complexity

Complexity cheat-sheet

The number that matters most in an interview is rarely the average case — it's whether you can name the worst case and explain when it happens.

Space column for Quick Sort is the recursion call stack, not extra array storage — it's in-place in the sense that it doesn't allocate another full array like Merge Sort does.

05 · Before you pick one

Common mistakes

• Picking Quick Sort's pivot naively as the first or last element — on an already-sorted (or reverse-sorted) array, this triggers the O(n²) worst case every single time instead of the average-case O(n log n).
• Assuming a sort is stable when it isn't. If your problem depends on equal-key elements keeping their original relative order (say, sorting orders by status while preserving arrival order within a status), an unstable sort like Quick Sort or Heap Sort will silently scramble that.
• Reaching for Counting Sort on a huge or effectively unbounded value range — its O(n+k) promise assumes k is small; if k is much bigger than n, you've traded time for a memory blow-up.
• Forgetting Merge Sort needs O(n) auxiliary space for the merge step — it's a real constraint if you're sorting under a tight memory budget, even though its time guarantee is excellent.
• Confusing average-case with worst-case guarantees when the choice actually matters — e.g. picking Quick Sort for a latency-sensitive system without acknowledging its worst case, instead of a guaranteed-O(n log n) option like Merge or Heap Sort.
• Treating all O(n²) sorts as interchangeable — Insertion Sort's adaptiveness on nearly-sorted data makes it a genuinely reasonable choice in that specific situation, unlike Bubble or Selection Sort.

06 · Pick the right tool

Pick the right one for the job

Eight algorithms, four families, one decision each time: what do you actually know about the data, and what are you optimizing for? Each card links to the matching interactive visualizer.