Advanced Sorting

Once you cross n = a few thousand, the O(n²) sorts become unusable and you reach for the O(n log n) family — Merge sort, Quicksort, Heap sort — plus the *non-comparison* sorts (Counting, Radix, Bucket) that beat the O(n log n) lower bound by exploiting the structure of the data. Every standard library sort you've ever called is one of these (or a hybrid of several).

What "Advanced Sorting" Actually Is

Three big ideas, each gives an O(n log n) algorithm:

1. Divide and Conquer → split the array, sort each half, *combine*. → Merge sort. 2. Partition → pick a pivot, put smaller things left, larger right, recurse. → Quicksort. 3. Heap → repeatedly pull the max out of a heap. → Heap sort.

A separate idea, breaking the comparison-based O(n log n) lower bound:

4. Don't compare elements at all → count, distribute, or bucket. → Counting / Radix / Bucket sort.

Real-world libraries (Timsort, Introsort, PDQSort) glue 2–3 of these together because no single algorithm wins on every input.

Daily Mental Model

• Merge sort — like collating two already-sorted decks of cards into one big sorted deck.
• Quicksort — pick any card as the "pivot", throw smaller ones to the left pile, larger to the right, then sort each pile the same way.
• Heap sort — dump everything into a priority queue, then drain it largest-first into the end of the array.

Beginner Mistakes to Skip

1. Picking the first element as the quicksort pivot on already-sorted data. Instant O(n²). Use random or median-of-three. 2. Forgetting merge sort needs O(n) extra memory. It's *not* in-place. If memory is tight, this rules it out. 3. Thinking quicksort is always faster than mergesort. True on average for arrays in RAM (cache locality), false for linked lists or external sorting (disk). 4. Using radix/counting sort on huge value ranges. Counting sort is O(n + k); if \k = 10⁹\, that's worse than n log n. 5. Assuming any sort you've heard of is stable. Quicksort and heapsort are not. If you sort by multiple keys, this matters. 6. Reimplementing your own sort in production. Standard libraries are *fast*, *correct*, and *adaptive*. The right answer is almost always \arr.sort(...)\.

Intermediate: Merge Sort

\\\`js function mergeSort(arr) { if (arr.length <= 1) return arr; const mid = arr.length >> 1; const left = mergeSort(arr.slice(0, mid)); const right = mergeSort(arr.slice(mid)); return merge(left, right); } function merge(a, b) { const out = []; let i = 0, j = 0; while (i < a.length && j < b.length) { if (a[i] <= b[j]) out.push(a[i++]); else out.push(b[j++]); } while (i < a.length) out.push(a[i++]); while (j < b.length) out.push(b[j++]); return out; } \\\`

• Time: O(n log n) always — best, average, worst. Predictable.
• Space: O(n) for the merge buffer.
• Stable: yes (the \<=\ in \merge\ preserves order of equal elements).
• Where it wins: linked lists (no random access needed), external sorting (you can merge from disk), parallelisable, guaranteed worst case.
• Bonus: counting inversions (pairs where i < j but arr[i] > arr[j]) in O(n log n) by adding a counter inside \merge\.

Intermediate: Quicksort

\\\`js function quicksort(arr, lo = 0, hi = arr.length - 1) { if (lo >= hi) return arr; const p = partition(arr, lo, hi); quicksort(arr, lo, p - 1); quicksort(arr, p + 1, hi); return arr; } // Lomuto partition with last element as pivot function partition(arr, lo, hi) { const pivot = arr[hi]; let i = lo; for (let j = lo; j < hi; j++) { if (arr[j] < pivot) { [arr[i], arr[j]] = [arr[j], arr[i]]; i++; } } [arr[i], arr[hi]] = [arr[hi], arr[i]]; return i; } \\\`

• Time: O(n log n) average / best, O(n²) worst (bad pivot — sorted input + first-element pivot).
• Space: O(log n) recursion stack (in-place partitioning).
• Stable: no (partition swaps non-adjacent elements).
• Why it's fast in practice: sequential memory access, tiny constants, in-place.

Lomuto vs Hoare partition: Lomuto is simpler (one pointer). Hoare uses two pointers from both ends, does ~3× fewer swaps on average — what real libraries use.

Intermediate: Heap Sort

\\\` heapSort(arr): buildMaxHeap(arr) // O(n) for i = n - 1 down to 1: swap(arr[0], arr[i]) // largest moves to position i heapifyDown(arr, 0, i) // restore heap on prefix [0..i) \\\`

• Time: O(n log n) guaranteed, no worst-case degradation.
• Space: O(1) — fully in-place.
• Stable: no.
• Cache behaviour: poor (parent/child indices jump around in memory) — usually slower than quicksort in practice despite same Big-O.
• Use case: when you need *both* O(n log n) guarantee *and* O(1) space (e.g., embedded systems).

Advanced: The Comparison Lower Bound (Ω(n log n))

Every comparison-based sort can be modeled as a binary decision tree where each leaf represents one of the n! possible orderings. Such a tree must have ≥ n! leaves, so its height ≥ log₂(n!) ≈ n log₂ n (Stirling). No comparison sort can beat O(n log n) in the worst case. Counting / Radix / Bucket dodge this because they don't compare elements — they exploit *structure*.

Advanced: Non-Comparison Sorts

Counting Sort — O(n + k), works when keys are integers in a known small range [0, k]:

\\\` count = array of size k+1, all zeros for x in arr: count[x]++ out = []; for v from 0 to k: repeat count[v] times: out.push(v) \\\`

Stable when implemented with prefix sums. Space O(k). Useless when k ≫ n (sorting 32-bit ints would need a 16 GB count array).

Radix Sort — O(d · (n + k)). Sort by each digit, least-significant first, using a stable sub-sort (counting sort). For fixed-width keys, d is a small constant → effectively O(n). Used in databases, graphics (z-buffer), GPU sorts.

Bucket Sort — O(n + k) average. Distribute elements into buckets based on value range, sort each bucket, concatenate. Best when input is uniformly distributed; worst case O(n²) when everything piles into one bucket.

Advanced: How Real-World Standard Libraries Sort

Practice Path

1. Implement merge sort with the recursive split + iterative merge. Test on \[]\, \[5]\, \[3,1,2,5,4]\. Then add an inversion counter — sort \[5,4,3,2,1]\ and confirm 10 inversions. 2. Implement quicksort with Lomuto partition and last-element pivot. Run it on \[1,2,3,…,1000]\. Then switch to random pivot — confirm runtime drops dramatically. 3. Implement counting sort. Use it inside a radix sort for an array of 4-digit integers. Time it vs quicksort on n = 100,000. 4. Sort an array of \{name, score}\ objects by \score\ using a stable sort — verify two equal scores keep their original order. Then do it with quicksort and confirm they don't.