Sorting Algorithms: Quick, Merge, Heap and Counting Sort

Sorting arranges items in order — smallest to largest, A to Z, oldest to newest. It is deeply studied because almost everything depends on it: searching is faster on sorted data, and many algorithms need sorted input. The four classics — quicksort, mergesort, heapsort, and counting sort — each solve sorting with a different clever idea.

Sorting matters far beyond the classroom. Sorting emails by date, ranking a leaderboard, or seeing "cheapest first" on a shopping site all ran a sorting algorithm. Knowing which to use — and why — separates a programmer who copies code from one who engineers performance.

Key Concepts

• Quicksort: pick a pivot, partition smaller elements left and larger right, recurse on each side. Average O(n log n), worst O(n²).
• Mergesort: split in half, sort each half, merge the sorted halves. Always O(n log n) but needs O(n) extra space.
• Heapsort: build a max-heap, repeatedly move the root (largest) to the end. Always O(n log n), O(1) extra space.
• Counting sort: for small-range integers, count occurrences of each value and write them out: O(n + k).
• Stable sort: equal elements keep their original order (mergesort, counting sort); quicksort and heapsort are not stable.
• Comparison lower bound: any comparison sort needs at least ~n log2 n comparisons; counting sort dodges this by not comparing.

Formulas

• Mergesort: T(n) = 2T(n/2) + O(n) = O(n log n) by the Master theorem.
• Quicksort: O(n log n) average with good pivots; T(n) = T(n−1) + O(n) = O(n²) with the worst pivot every time.
• Heapsort: O(n) to build the heap plus n extractions at O(log n) — O(n log n) worst case, O(1) space.
• Counting sort: O(n + k) time, O(k) space, where k = max − min + 1. For 1,000 marks in range 0–100 that is ~1,100 steps versus ~10,000 comparisons.
• Assumptions: quicksort's average case assumes reasonable pivots (randomised pivot achieves this); counting sort needs small-range integer keys.

Worked Example

Mergesort on [38, 27, 43, 3, 9, 82, 10]: split into [38, 27, 43, 3] and [9, 82, 10]; then [38, 27], [43, 3], [9], [82, 10]. Sort pairs → [27, 38], [3, 43], [9], [10, 82]. Merge [27, 38] with [3, 43] → [3, 27, 38, 43]; merge [9] with [10, 82] → [9, 10, 82]. Final merge → [3, 9, 10, 27, 38, 43, 82], each merge a linear scan. Counting sort on [4, 2, 2, 8, 3, 3, 1] (range 1–8): counts are 1→1, 2→2, 3→2, 4→1, 8→1, rest 0. Write out: [1, 2, 2, 3, 3, 4, 8] — zero comparisons, about n + k = 15 steps.

Common Misconceptions

• "Quicksort is always fastest." Not on already-sorted data with a naive pivot — O(n²). Libraries randomise the pivot or fall back to heapsort (introsort).
• "O(n log n) is the fastest possible." Only for comparison sorts; counting sort beats it when the range k is small.
• "Mergesort is useless because of extra memory." Wrong — its O(n) space buys guaranteed O(n log n) time and stability, ideal for linked lists and huge files.

Real-World Applications

• Quicksort: default in-memory sort in many language libraries (as introsort).
• Mergesort: sorting linked lists, external sorting of huge files, Java's object sort.
• Heapsort: embedded systems needing worst-case guarantees with tight memory.
• Counting sort: exam marks, ages, and small-range integers; a subroutine of radix sort.

Quicksort partitions around a pivot, mergesort divides and merges, heapsort extracts the maximum repeatedly, and counting sort counts instead of comparing. Know their time, space, and stability trade-offs, and you will always pick the right tool.