Sorting I

Imagine you have a row of playing cards face-up on a table and you want to arrange them from smallest to largest. Selection Sort works like this: scan all the cards to find the smallest one, then swap it with the first card. Now the first position is correct. Next, scan the remaining cards (positions 2 onward) to find the next smallest, and swap it into position 2. Repeat until every card is in the right place. The downside? Even if the cards are already mostly sorted, Selection Sort still scans through everything — it always does the same number of comparisons, making it O(n²) no matter what.

Insertion Sort works the way most people sort a hand of playing cards. You hold a sorted portion in your left hand and pick up one new card at a time with your right hand. For each new card, you slide it into the correct position among the cards already in your left hand. The algorithm does the same thing with an array: it starts from the second element, compares it with elements to its left, and shifts larger elements to the right until the correct spot is found. The beauty of Insertion Sort is that if the data is already nearly sorted, very few shifts are needed, making it run in O(n) — linear time. However, in the worst case (a reverse-sorted array), every element must be shifted all the way to the front, resulting in O(n²) time.

Merge Sort introduces one of the most powerful ideas in computer science: divide and conquer. Instead of trying to sort the whole array at once, you split it in half, sort each half separately (by applying the same strategy recursively), and then merge the two sorted halves back together. The merging step is the clever part — since both halves are already sorted, you just compare the front elements of each half, take the smaller one, and repeat. This guarantee of O(n log n) time makes Merge Sort much faster than Selection Sort or Insertion Sort for large inputs. The trade-off is that it needs O(n) extra memory to hold temporary copies during merging, so it is not 'in-place.'

QuickSort is arguably the most widely used sorting algorithm in practice. Like Merge Sort, it uses divide and conquer, but with a twist: instead of splitting the array in the middle, it picks a pivot element and partitions the array so that everything smaller than the pivot goes to its left and everything larger goes to its right. After partitioning, the pivot is in its final sorted position. Then QuickSort recursively sorts the left and right portions.

The most common partition scheme is Lomuto partition: use the last element as the pivot, maintain a boundary index $i$, and scan through the array. Each time you find an element ≤ pivot, swap it to the boundary and advance $i$. At the end, swap the pivot into position $i+1$.

Worked example — Lomuto partition on [7, 2, 1, 8, 6, 3, 5, 4] with pivot 4:

• -Start: $i = -1$, scan from left
• -$j=0$: 7 > 4 → skip
• -$j=1$: 2 ≤ 4 → $i=0$, swap A[0]↔A[1] → [2, 7, 1, 8, 6, 3, 5, 4]
• -$j=2$: 1 ≤ 4 → $i=1$, swap A[1]↔A[2] → [2, 1, 7, 8, 6, 3, 5, 4]
• -$j=3$: 8 > 4 → skip
• -$j=4$: 6 > 4 → skip
• -$j=5$: 3 ≤ 4 → $i=2$, swap A[2]↔A[5] → [2, 1, 3, 8, 6, 7, 5, 4]
• -Final: swap pivot A[7] with A[$i+1$]=A[3] → [2, 1, 3, 4, 6, 7, 5, 8]
• -Pivot 4 is now at index 3 — its correct sorted position!

QuickSort's average case is $O(n \log n)$ because a random pivot typically splits the array roughly in half. But if the pivot is consistently the smallest or largest element (e.g., already sorted input with last-element pivot), the split is maximally unbalanced ($n-1$ vs $0$), giving $O(n^2)$ worst case. Randomized QuickSort fixes this by choosing the pivot randomly, making the $O(n^2)$ case astronomically unlikely.

Here is a surprising theoretical result: no matter how clever you are, if your sorting algorithm works by comparing pairs of elements (like all the algorithms we have seen so far), it must make at least Ω(n log n) comparisons in the worst case. How do we know this? We can model every possible comparison-based algorithm as a 'decision tree' — a branching diagram where each internal node represents a comparison (is A[i] < A[j]?), each branch represents the outcome (yes or no), and each leaf represents a final sorted order. Since there are n! (n factorial) possible ways to arrange n items, the tree must have at least n! leaves. The minimum height of a binary tree with n! leaves is log₂(n!), which by Stirling's approximation equals Ω(n log n). This means algorithms like Merge Sort and Heap Sort are optimal — they hit this theoretical speed limit.

If the $\Omega(n \log n)$ lower bound says no comparison sort can do better, how can we sort faster? The answer is: stop comparing! Counting Sort does not compare elements at all — instead, it counts how many times each value appears. If you know all values fall in the range $0$ to $k$, you create a count array of size $k+1$, scan the input to fill the counts, compute prefix sums (so you know where each value belongs in the output), and place each element directly into its correct position. The total time is $O(n + k)$: $O(n)$ to count, $O(k)$ for prefix sums, and $O(n)$ to place. When $k = O(n)$, this is $O(n)$ — faster than any comparison sort! The catch: if $k$ is huge (like sorting 32-bit integers where $k = 2^{32}$), the count array becomes impractically large.