Sorting is one of those topics that seems simple on the surface. You have a bunch of things, you put them in order, done. But underneath that simplicity is an entire universe of computer science: divide and conquer, recursion, stability, partitioning, heaps, counting tricks, and trade-offs that have occupied brilliant minds for decades. Here's the thing: sorting is not just about putting numbers in order. It's a **gateway** to understanding how algorithms are designed, analyzed, and compared. When you study sorting, you're really studying **algorithm design patterns** that show up everywhere else in computer science. Think about it. Merge sort teaches you **divide and conquer**. Quick sort teaches you **partitioning**. Heap sort teaches you **priority queues**. Counting sort teaches you that sometimes you can beat O(n log n) by exploiting constraints. And insertion sort teaches you that the “slow” algorithm is sometimes the fastest choice. > Sorting algorithms are the fruit flies of computer science: small, well-studied, and endlessly revealing about the nature of computation itself. And let's talk about the practical side. If you've ever written `[10, 9, 1, 2, 3].sort()` in JavaScript and gotten `[1, 10, 2, 3, 9]` back, you already know that understanding sorting matters in the real world too. JavaScript's `.sort()` has quirks that trip up even experienced developers, and knowing *why* helps you avoid nasty bugs. By the end of this guide, you'll: - Understand **every major sorting algorithm** and how it works under the hood - Be able to implement each one in **TypeScript** from scratch - Know the **Big O** complexity (best, average, worst) for every algorithm - Understand **stability** and why it matters - Have a **decision framework** for choosing the right sort for any situation - Be ready to handle **sorting-related interview problems** Let's dive in. --- ## What Makes a Good Sorting Algorithm? Before we look at individual algorithms, we need to establish the criteria for evaluating them. Not all sorts are created equal, and the “best” algorithm depends entirely on what you're optimizing for. ### Time Complexity The most obvious metric. How many comparisons and swaps does the algorithm perform as the input grows? - **Best case**: The input is already favorable (often already sorted) - **Average case**: Random input, the most realistic scenario - **Worst case**: The input is adversarial (often reverse-sorted or has many duplicates) The theoretical lower bound for comparison-based sorting is **O(n log n)**. You literally cannot sort faster than this if your only tool is comparing pairs of elements. This is provable via decision tree analysis: with n! possible permutations, you need at least log₂(n!) comparisons, which is O(n log n). But here's the twist: non-comparison sorts like counting sort and radix sort can beat this bound by exploiting properties of the data itself. ### Space Complexity How much extra memory does the algorithm need beyond the input array? - **In-place**: O(1) extra space (or O(log n) for the call stack). The sort rearranges elements within the original array. - **Out-of-place**: O(n) extra space. The sort needs a separate array to work. In-place sorting is preferred when memory is tight, but out-of-place sorts like merge sort can be more cache-friendly and stable. ### Stability A sorting algorithm is **stable** if it preserves the relative order of elements that have equal keys. Why does this matter? Imagine you have a list of employees sorted by name, and then you sort by department: ``` Before (sorted by name): Alice - Engineering Bob - Marketing Charlie - Engineering Diana - Marketing Stable sort by department: Alice - Engineering ← Alice before Charlie (original order preserved) Charlie - Engineering Bob - Marketing ← Bob before Diana (original order preserved) Diana - Marketing Unstable sort by department: Charlie - Engineering ← Charlie before Alice (original order NOT preserved) Alice - Engineering Diana - Marketing ← Diana before Bob (original order NOT preserved) Bob - Marketing ``` With a **stable** sort, Alice stays before Charlie (both in Engineering), and Bob stays before Diana (both in Marketing), because that was their original order. An **unstable** sort might rearrange them arbitrarily. Stability matters when you're doing **multi-key sorts** (sort by one field, then another), working with **objects** where the sort key doesn't fully determine order, or when **predictability** is important. ### Adaptivity An **adaptive** algorithm runs faster when the input is already partially sorted. Insertion sort is the classic example: it's O(n) on nearly sorted data, which is why it's used as a building block inside more sophisticated algorithms like TimSort. Non-adaptive algorithms (like selection sort or heap sort) always take the same time regardless of the input's initial order. ### Summary of Properties | Property | What It Means | Why It Matters | |---------------|--------------------------------------------------|-----------------------------------------| | Time | Comparisons/swaps as input grows | Speed | | Space | Extra memory needed | Memory constraints | | Stability | Equal elements keep original order | Multi-key sorts, predictability | | Adaptivity | Faster on partially sorted input | Real-world data is often nearly sorted | | In-place | Works within the original array | Low memory overhead | --- ## JavaScript's Built-in `.sort()` Before we build our own sorting algorithms, let's talk about the one you probably use every day. ### The Classic Gotcha ```typescript const nums = [10, 9, 1, 2, 3]; console.log(nums.sort()); // Output: [1, 10, 2, 3, 9] ← NOT what you expected! ``` JavaScript's `.sort()` converts elements to **strings** by default and sorts them **lexicographically**. So `10` comes before `2` because the string `"10"` comes before `"2"` (it compares character by character: `'1'` < `'2'`). The fix is to always pass a **comparator function**: ```typescript const nums = [10, 9, 1, 2, 3]; // Ascending nums.sort((a, b) => a - b); // [1, 2, 3, 9, 10] // Descending nums.sort((a, b) => b - a); // [10, 9, 3, 2, 1] ``` The comparator returns: - **Negative** → `a` comes first - **Zero** → keep original order (if stable) - **Positive** → `b` comes first ### What's Actually Under the Hood? Modern JavaScript engines use **TimSort**, a hybrid algorithm invented by Tim Peters in 2002 for Python. V8 (Chrome, Node.js) switched from QuickSort to TimSort in 2019. TimSort combines **merge sort** and **insertion sort**: 1. Divide the array into small chunks called “runs” 2. Sort each run with **insertion sort** (fast for small arrays) 3. Merge the runs using a modified **merge sort** It's stable, adaptive, and has O(n log n) worst-case time. It's essentially the best general-purpose sorting algorithm we know of, which is why it's the default in JavaScript, Python, Java (for objects), and many other languages. ### When Do You Need Something Else? JavaScript's `.sort()` is great for general use, but there are situations where you might want a different algorithm: - **Performance-critical code**: You know something specific about your data (bounded integers, nearly sorted) that a specialized sort could exploit - **Stable sort guarantee**: While modern engines use TimSort (stable), the spec didn't require stability until ES2019, and some environments might lag behind - **Learning and interviews**: You need to implement a sort from scratch - **Custom data structures**: You're sorting linked lists, external files, or streaming data Now let's build every major sorting algorithm from the ground up. --- ## The Simple Sorts — O(n²) These are the algorithms you learn first. They're slow for large inputs, but they're simple to understand, easy to implement, and sometimes the best choice for small or nearly sorted data. The common thread: they all use **nested loops**, leading to quadratic time complexity. --- ### Bubble Sort Bubble sort is the simplest sorting algorithm. It repeatedly walks through the list, compares adjacent elements, and swaps them if they're in the wrong order. The largest unsorted element “bubbles up” to its correct position on each pass. **How it works:** 1. Start at the beginning of the array 2. Compare each pair of adjacent elements 3. If the left element is greater than the right, swap them 4. After one complete pass, the largest element is in its final position 5. Repeat for the remaining unsorted portion 6. Stop when no swaps are made in a complete pass (optimization) #### Visual Walkthrough Let's sort `[5, 3, 8, 1, 2]`: ``` Pass 1: [5, 3, 8, 1, 2] compare 5 and 3 → swap [3, 5, 8, 1, 2] compare 5 and 8 → no swap [3, 5, 8, 1, 2] compare 8 and 1 → swap [3, 5, 1, 8, 2] compare 8 and 2 → swap [3, 5, 1, 2, 8] ✓ 8 is in final position Pass 2: [3, 5, 1, 2, 8] compare 3 and 5 → no swap [3, 5, 1, 2, 8] compare 5 and 1 → swap [3, 1, 5, 2, 8] compare 5 and 2 → swap [3, 1, 2, 5, 8] ✓ 5 is in final position Pass 3: [3, 1, 2, 5, 8] compare 3 and 1 → swap [1, 3, 2, 5, 8] compare 3 and 2 → swap [1, 2, 3, 5, 8] ✓ 3 is in final position Pass 4: [1, 2, 3, 5, 8] compare 1 and 2 → no swap [1, 2, 3, 5, 8] no swaps made → DONE! Result: [1, 2, 3, 5, 8] ``` Notice how on each pass, the largest unsorted element floats to the right like a bubble rising to the surface. #### TypeScript Implementation ```typescript function bubbleSort(arr: number[]): number[] { const n = arr.length; for (let i = 0; i < n - 1; i++) { let swapped = false; for (let j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; swapped = true; } } if (!swapped) break; } return arr; } ``` The `swapped` flag is the key optimization. If we make a complete pass without any swaps, the array is sorted and we can stop early. This makes bubble sort O(n) on already-sorted input. #### Complexity Analysis | Case | Time | Why | |---------|--------|--------------------------------------------------| | Best | O(n) | Already sorted, one pass with no swaps | | Average | O(n²) | Roughly n²/2 comparisons and swaps | | Worst | O(n²) | Reverse sorted, every pair needs swapping | - **Space**: O(1) — in-place - **Stable**: Yes (equal elements never swap) - **Adaptive**: Yes (with the `swapped` optimization) #### When Is Bubble Sort Useful? Almost never in production. But it has two niche uses: 1. **Teaching**: It's the simplest sort to understand and implement 2. **Nearly sorted data**: With the early exit optimization, it's O(n) when the array is nearly sorted. However, insertion sort is strictly better for this case. --- ### Selection Sort Selection sort works by repeatedly finding the **minimum** element from the unsorted portion and placing it at the beginning. **How it works:** 1. Find the smallest element in the entire array 2. Swap it with the first element 3. Find the smallest element in the remaining unsorted portion 4. Swap it with the second element 5. Repeat until the entire array is sorted #### Visual Walkthrough Let's sort `[29, 10, 14, 37, 13]`: ``` Step 1: Find minimum in [29, 10, 14, 37, 13] → 10 (index 1) Swap arr[0] and arr[1] [10, 29, 14, 37, 13] ✓ Step 2: Find minimum in [29, 14, 37, 13] → 13 (index 4) Swap arr[1] and arr[4] [10, 13, 14, 37, 29] ✓ ✓ Step 3: Find minimum in [14, 37, 29] → 14 (index 2) Already in place, no swap needed [10, 13, 14, 37, 29] ✓ ✓ ✓ Step 4: Find minimum in [37, 29] → 29 (index 4) Swap arr[3] and arr[4] [10, 13, 14, 29, 37] ✓ ✓ ✓ ✓ ✓ Result: [10, 13, 14, 29, 37] ``` #### TypeScript Implementation ```typescript function selectionSort(arr: number[]): number[] { const n = arr.length; for (let i = 0; i < n - 1; i++) { let minIndex = i; for (let j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } if (minIndex !== i) { [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; } } return arr; } ``` #### Complexity Analysis | Case | Time | Why | |---------|--------|--------------------------------------------------| | Best | O(n²) | Always scans the entire unsorted portion | | Average | O(n²) | Same number of comparisons regardless | | Worst | O(n²) | Same number of comparisons regardless | - **Space**: O(1) — in-place - **Stable**: No (the swap can change the relative order of equal elements) - **Adaptive**: No (always does the same number of comparisons) #### The Swap Advantage Selection sort always performs **at most n-1 swaps**, regardless of the input. This makes it useful when **writes are expensive** (e.g., writing to flash memory or when swap operations are costly). Compare this to bubble sort, which might perform O(n²) swaps. However, selection sort always does O(n²) comparisons, so it's not adaptive and never benefits from partially sorted input. > Selection sort: minimum comparisons? No. Minimum swaps? Yes. --- ### Insertion Sort Insertion sort is the **card player's algorithm**. Think about how you sort a hand of playing cards: you pick up one card at a time and insert it into its correct position among the cards you've already sorted. **How it works:** 1. Start with the second element (the first element is already “sorted”) 2. Compare it with elements to its left 3. Shift larger elements to the right to make room 4. Insert the element in its correct position 5. Repeat for all remaining elements #### Visual Walkthrough Let's sort `[5, 2, 4, 6, 1, 3]`: ``` Start: [5, 2, 4, 6, 1, 3] ─ Step 1: key = 2, insert into [5] 2 < 5 → shift 5 right [2, 5, 4, 6, 1, 3] ──── Step 2: key = 4, insert into [2, 5] 4 < 5 → shift 5 right 4 > 2 → stop [2, 4, 5, 6, 1, 3] ─────── Step 3: key = 6, insert into [2, 4, 5] 6 > 5 → already in place [2, 4, 5, 6, 1, 3] ────────── Step 4: key = 1, insert into [2, 4, 5, 6] 1 < 6 → shift 6 right 1 < 5 → shift 5 right 1 < 4 → shift 4 right 1 < 2 → shift 2 right [1, 2, 4, 5, 6, 3] ───────────── Step 5: key = 3, insert into [1, 2, 4, 5, 6] 3 < 6 → shift 6 right 3 < 5 → shift 5 right 3 < 4 → shift 4 right 3 > 2 → stop [1, 2, 3, 4, 5, 6] ──────────────── Result: [1, 2, 3, 4, 5, 6] ``` #### TypeScript Implementation ```typescript function insertionSort(arr: number[]): number[] { const n = arr.length; for (let i = 1; i < n; i++) { const key = arr[i]; let j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } return arr; } ``` #### Complexity Analysis | Case | Time | Why | |---------|--------|--------------------------------------------------| | Best | O(n) | Already sorted, inner loop never executes | | Average | O(n²) | On average, each element shifts halfway back | | Worst | O(n²) | Reverse sorted, each element shifts all the way | - **Space**: O(1) — in-place - **Stable**: Yes (equal elements maintain their relative order) - **Adaptive**: Yes (fewer shifts when data is nearly sorted) #### Why Insertion Sort Matters Insertion sort might seem like just another O(n²) algorithm, but it has unique properties that make it genuinely important: 1. **Best for small arrays**: For arrays under ~20-50 elements, insertion sort outperforms merge sort and quick sort because it has very low overhead (no recursion, no auxiliary arrays, tight inner loop). 2. **Best for nearly sorted data**: When elements are close to their final position, insertion sort is nearly O(n). This happens more often than you'd think in real-world data. 3. **Used inside TimSort**: Python and JavaScript's built-in sort uses insertion sort for small runs (typically 32-64 elements) before merging them. This hybrid approach gets the best of both worlds. 4. **Online algorithm**: Insertion sort can sort data as it arrives. You don't need the entire input upfront, making it useful for streaming scenarios. > Insertion sort is the unsung hero of sorting. It's the algorithm that makes other algorithms fast. --- ## The Efficient Sorts — O(n log n) These are the workhorses. They're fast enough for most real-world applications and form the backbone of production sorting implementations. The O(n log n) bound comes from the mathematical fact that you need at least that many comparisons to distinguish between all n! possible permutations. --- ### Merge Sort Merge sort is the quintessential **divide and conquer** algorithm. It splits the array in half, recursively sorts each half, and then merges the two sorted halves together. The key insight: **merging two sorted arrays into one sorted array is an O(n) operation**. If you keep splitting until you have arrays of size 1 (which are trivially sorted), then merging them back together gives you a fully sorted array. The splitting creates O(log n) levels, and each level does O(n) work during merging, giving O(n log n) total. **How it works:** 1. If the array has 0 or 1 elements, it's already sorted. Return it. 2. Split the array into two halves. 3. Recursively sort each half. 4. Merge the two sorted halves into a single sorted array. #### Visual Walkthrough Let's sort `[38, 27, 43, 3, 9, 82, 10]`: ``` Split Phase (divide): [38, 27, 43, 3, 9, 82, 10] / \ [38, 27, 43, 3] [9, 82, 10] / \ / \ [38, 27] [43, 3] [9, 82] [10] / \ / \ / \ | [38] [27] [43] [3] [9] [82] [10] Merge Phase (conquer): [38] [27] [43] [3] [9] [82] [10] \ / \ / \ / | [27, 38] [3, 43] [9, 82] [10] \ / \ / [3, 27, 38, 43] [9, 10, 82] \ / [3, 9, 10, 27, 38, 43, 82] ``` Let's zoom into one merge to see the detail. Merging `[3, 27, 38, 43]` and `[9, 10, 82]`: ``` Left: [3, 27, 38, 43] Right: [9, 10, 82] Result: [] ^ ^ Compare 3 and 9 → take 3 Left: [3, 27, 38, 43] Right: [9, 10, 82] Result: [3] ^ ^ Compare 27 and 9 → take 9 Left: [3, 27, 38, 43] Right: [9, 10, 82] Result: [3, 9] ^ ^ Compare 27 and 10 → take 10 Left: [3, 27, 38, 43] Right: [9, 10, 82] Result: [3, 9, 10] ^ ^ Compare 27 and 82 → take 27 Left: [3, 27, 38, 43] Right: [9, 10, 82] Result: [3, 9, 10, 27] ^ ^ Compare 38 and 82 → take 38 Left: [3, 27, 38, 43] Right: [9, 10, 82] Result: [3, 9, 10, 27, 38] ^ ^ Compare 43 and 82 → take 43 Left exhausted → append remaining right Result: [3, 9, 10, 27, 38, 43, 82] ``` #### TypeScript Implementation ```typescript function mergeSort(arr: number[]): number[] { if (arr.length <= 1) return arr; const mid = Math.floor(arr.length / 2); const left = mergeSort(arr.slice(0, mid)); const right = mergeSort(arr.slice(mid)); return merge(left, right); } function merge(left: number[], right: number[]): number[] { const result: number[] = []; let i = 0; let j = 0; while (i < left.length && j < right.length) { if (left[i] <= right[j]) { result.push(left[i]); i++; } else { result.push(right[j]); j++; } } while (i < left.length) { result.push(left[i]); i++; } while (j < right.length) { result.push(right[j]); j++; } return result; } ``` Note the `<=` in the merge function: `left[i] <= right[j]`. This is what makes merge sort **stable**. When elements are equal, we take from the left array first, preserving their original relative order. #### Complexity Analysis | Case | Time | Why | |---------|------------|----------------------------------------------| | Best | O(n log n) | Always splits and merges | | Average | O(n log n) | Same work regardless of input | | Worst | O(n log n) | Same work regardless of input | - **Space**: O(n) — needs auxiliary arrays for merging - **Stable**: Yes (with `<=` in merge comparison) - **Adaptive**: No (always does the same work) #### When to Use Merge Sort - **Stability required**: Merge sort is the go-to stable O(n log n) sort - **Linked lists**: Merge sort is ideal for linked lists because merging doesn't require random access, and the split can be done with slow/fast pointers. No extra space needed! - **External sorting**: When data doesn't fit in memory (sorting files on disk), merge sort's sequential access pattern is perfect - **Guaranteed O(n log n)**: Unlike quick sort, merge sort never degrades to O(n²) The downside: it needs O(n) extra space for arrays. That's a real cost when you're sorting millions of elements. --- ### Quick Sort Quick sort is often the **fastest sorting algorithm in practice**, which is why it was the default in many languages before TimSort took over. It's another divide and conquer algorithm, but instead of splitting the array in half and merging, it **partitions** the array around a pivot element. **How it works:** 1. Choose a **pivot** element from the array 2. **Partition** the array: move all elements smaller than the pivot to the left, and all elements larger to the right 3. The pivot is now in its final sorted position 4. Recursively sort the left and right subarrays The magic is in the partition step. After partitioning, the pivot is in exactly the right place, and we never need to touch it again. #### Pivot Selection Strategies The choice of pivot dramatically affects performance: - **First element**: Simple but terrible for sorted/nearly sorted arrays (O(n²)) - **Last element**: Same problem as first - **Random element**: Good average-case behavior, avoids worst case with high probability - **Median-of-three**: Take the median of the first, middle, and last elements. Good balance of simplicity and performance. ```typescript function medianOfThree(arr: number[], lo: number, hi: number): number { const mid = Math.floor((lo + hi) / 2); if (arr[lo] > arr[mid]) [arr[lo], arr[mid]] = [arr[mid], arr[lo]]; if (arr[lo] > arr[hi]) [arr[lo], arr[hi]] = [arr[hi], arr[lo]]; if (arr[mid] > arr[hi]) [arr[mid], arr[hi]] = [arr[hi], arr[mid]]; return mid; } ``` #### Partition Schemes: Lomuto vs Hoare There are two classic ways to partition. **Lomuto partition** (simpler, slightly slower): Uses a single pointer that scans from left to right, maintaining the invariant that everything before the pointer is less than the pivot. ```typescript function lomutoPartition(arr: number[], lo: number, hi: number): number { const pivot = arr[hi]; let i = lo - 1; for (let j = lo; j < hi; j++) { if (arr[j] <= pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; } } [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]]; return i + 1; } ``` **Hoare partition** (faster, trickier): Uses two pointers that move toward each other from both ends. ```typescript function hoarePartition(arr: number[], lo: number, hi: number): number { const pivot = arr[Math.floor((lo + hi) / 2)]; let i = lo - 1; let j = hi + 1; while (true) { do { i++; } while (arr[i] < pivot); do { j--; } while (arr[j] > pivot); if (i >= j) return j; [arr[i], arr[j]] = [arr[j], arr[i]]; } } ``` Hoare's partition does about 3x fewer swaps on average and handles duplicates better. #### Visual Walkthrough (Lomuto Partition) Let's sort `[7, 2, 1, 6, 8, 5, 3, 4]` using last element as pivot: ``` Partition with pivot = 4: [7, 2, 1, 6, 8, 5, 3, 4] j pivot=4 i=-1 j=0: 7 > 4, skip j=1: 2 ≤ 4, i=0, swap arr[0] and arr[1] [2, 7, 1, 6, 8, 5, 3, 4] j=2: 1 ≤ 4, i=1, swap arr[1] and arr[2] [2, 1, 7, 6, 8, 5, 3, 4] j=3: 6 > 4, skip j=4: 8 > 4, skip j=5: 5 > 4, skip j=6: 3 ≤ 4, i=2, swap arr[2] and arr[6] [2, 1, 3, 6, 8, 5, 7, 4] Final: swap arr[i+1]=arr[3] and arr[hi]=arr[7] (pivot) [2, 1, 3, 4, 8, 5, 7, 6] ↑ pivot in final position! Left: [2, 1, 3] (all ≤ 4) Right: [8, 5, 7, 6] (all > 4) Now recursively sort left and right subarrays... ``` #### TypeScript Implementation ```typescript function quickSort(arr: number[], lo = 0, hi = arr.length - 1): number[] { if (lo < hi) { const pivotIndex = partition(arr, lo, hi); quickSort(arr, lo, pivotIndex - 1); quickSort(arr, pivotIndex + 1, hi); } return arr; } function partition(arr: number[], lo: number, hi: number): number { const randomIndex = lo + Math.floor(Math.random() * (hi - lo + 1)); [arr[randomIndex], arr[hi]] = [arr[hi], arr[randomIndex]]; const pivot = arr[hi]; let i = lo - 1; for (let j = lo; j < hi; j++) { if (arr[j] <= pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; } } [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]]; return i + 1; } ``` We use **random pivot selection** to avoid the O(n²) worst case. By randomly choosing which element to partition around, the probability of consistently hitting the worst case becomes astronomically small. #### Complexity Analysis | Case | Time | Why | |---------|------------|--------------------------------------------------| | Best | O(n log n) | Pivot always splits evenly | | Average | O(n log n) | Random pivot gives balanced splits on average | | Worst | O(n²) | Pivot is always the min or max (degenerate) | - **Space**: O(log n) average for the call stack (O(n) worst case) - **Stable**: No (partitioning swaps non-adjacent elements) - **Adaptive**: No #### The Worst Case and How to Avoid It Quick sort's O(n²) worst case happens when the pivot is always the smallest or largest element, creating maximally unbalanced partitions. This occurs with: - Already sorted input + first/last element as pivot - All identical elements (without 3-way partition) Mitigation strategies: 1. **Random pivot**: Makes worst case extremely unlikely 2. **Median-of-three**: Good practical choice 3. **Introsort**: Switch to heap sort if recursion depth exceeds 2 * log(n). This is what C++'s `std::sort` uses. 4. **3-way partition**: Handle duplicates efficiently (Dutch National Flag) #### When to Use Quick Sort - **General purpose in-place sorting**: Quick sort uses only O(log n) extra space for the call stack - **Cache performance**: Quick sort works on contiguous memory with good locality - **Average case speed**: Quick sort is often faster than merge sort in practice due to lower constant factors and better cache behavior --- ### Heap Sort Heap sort uses a **binary heap** data structure to sort elements. It works by building a max-heap from the array, then repeatedly extracting the maximum element. If you're not familiar with heaps, here's the quick version: a **max-heap** is a complete binary tree where every parent is greater than or equal to its children. The largest element is always at the root. In an array representation of a heap: - Parent of index `i`: `Math.floor((i - 1) / 2)` - Left child of index `i`: `2 * i + 1` - Right child of index `i`: `2 * i + 2` **How it works:** 1. Build a max-heap from the array (in-place, O(n)) 2. Swap the root (maximum) with the last element 3. Reduce the heap size by one 4. Heapify the root to restore the heap property 5. Repeat until the heap is empty #### Visual Walkthrough Let's sort `[4, 10, 3, 5, 1]`: ``` Step 1: Build max-heap Array: [4, 10, 3, 5, 1] As a tree: 4 / \ 10 3 / \ 5 1 Heapify from last non-leaf (index 1): Index 1 (10): children are 5, 1. 10 > both. OK. Index 0 (4): children are 10, 3. 10 > 4. Swap. 10 / \ 4 3 → 4 has children 5, 1. 5 > 4. Swap. / \ 5 1 10 / \ 5 3 / \ 4 1 Max-heap array: [10, 5, 3, 4, 1] Step 2: Extract max elements Swap root (10) with last element (1): [1, 5, 3, 4, 10] heap size = 4 ✓ 10 is sorted Heapify root: [5, 4, 3, 1, | 10] ✓ Swap root (5) with last in heap (1): [1, 4, 3, 5, | 10] heap size = 3 Heapify root: [4, 1, 3, | 5, 10] ✓ Swap root (4) with last in heap (3): [3, 1, 4, | 5, 10] heap size = 2 Heapify root: [3, 1, | 4, 5, 10] ✓ Swap root (3) with last in heap (1): [1, 3, | 4, 5, 10] heap size = 1 Done! Result: [1, 3, 4, 5, 10] ``` #### TypeScript Implementation ```typescript function heapSort(arr: number[]): number[] { const n = arr.length; for (let i = Math.floor(n / 2) - 1; i >= 0; i--) { heapify(arr, n, i); } for (let i = n - 1; i > 0; i--) { [arr[0], arr[i]] = [arr[i], arr[0]]; heapify(arr, i, 0); } return arr; } function heapify(arr: number[], heapSize: number, rootIndex: number): void { let largest = rootIndex; const left = 2 * rootIndex + 1; const right = 2 * rootIndex + 2; if (left < heapSize && arr[left] > arr[largest]) { largest = left; } if (right < heapSize && arr[right] > arr[largest]) { largest = right; } if (largest !== rootIndex) { [arr[rootIndex], arr[largest]] = [arr[largest], arr[rootIndex]]; heapify(arr, heapSize, largest); } } ``` #### Why Building a Heap Is O(n), Not O(n log n) A common misconception is that building a heap takes O(n log n) because you call heapify (O(log n)) for each of the n/2 nodes. But the actual cost is O(n) because most nodes are near the bottom of the tree and barely need to move. The math: the number of nodes at height h is at most n / 2^(h+1), and each does O(h) work. Summing over all heights gives O(n). #### Complexity Analysis | Case | Time | Why | |---------|------------|----------------------------------------------| | Best | O(n log n) | Always builds heap and extracts | | Average | O(n log n) | Same work regardless | | Worst | O(n log n) | Same work regardless | - **Space**: O(1) — in-place (the heap is built within the array) - **Stable**: No (heap operations can rearrange equal elements) - **Adaptive**: No #### Trade-offs Heap sort has a guaranteed O(n log n) worst case with O(1) extra space — a combination no other comparison sort achieves. But it has downsides: - **Not cache-friendly**: Heap operations jump around in memory (parent to child indices are far apart), leading to many cache misses - **Not stable**: If you need to preserve the order of equal elements, heap sort won't work - **Slower constant factors**: In practice, quick sort is usually 2-3x faster due to better cache locality Heap sort is most useful as a **fallback**. Introsort (used in C++'s `std::sort`) starts with quick sort and switches to heap sort if the recursion depth gets too deep, combining quick sort's average-case speed with heap sort's worst-case guarantee. --- ## The Linear Sorts — O(n) Wait, didn't we say O(n log n) was the lower bound? Yes — for **comparison-based** sorts. These algorithms cheat: they don't compare elements to each other. Instead, they exploit specific properties of the input data (like bounded integer range or digit structure) to sort without comparisons. The trade-off: they only work under certain conditions. --- ### Counting Sort Counting sort works by **counting the occurrences** of each distinct element and then computing positions. It's incredibly fast when the range of input values (k) is not significantly larger than the number of elements (n). **How it works:** 1. Find the range of input values (min to max) 2. Create a count array of size `max - min + 1` 3. Count occurrences of each value 4. Compute prefix sums (cumulative counts) to determine positions 5. Build the output array by placing each element at its computed position #### Visual Walkthrough Let's sort `[4, 2, 2, 8, 3, 3, 1]`: ``` Input: [4, 2, 2, 8, 3, 3, 1] Range: 1 to 8 Step 1: Count occurrences Value: 1 2 3 4 5 6 7 8 Count: [1, 2, 2, 1, 0, 0, 0, 1] Step 2: Prefix sums (cumulative count) Value: 1 2 3 4 5 6 7 8 Count: [1, 3, 5, 6, 6, 6, 6, 7] This tells us: "1" ends at position 1, "2"s end at position 3, "3"s end at position 5, etc. Step 3: Build output (iterate input from right to left for stability) Process 1 (input[6]): count[1]=1, place at index 0, count[1]=0 Output: [1, _, _, _, _, _, _] Process 3 (input[5]): count[3]=5, place at index 4, count[3]=4 Output: [1, _, _, _, 3, _, _] Process 3 (input[4]): count[3]=4, place at index 3, count[3]=3 Output: [1, _, _, 3, 3, _, _] Process 8 (input[3]): count[8]=7, place at index 6, count[8]=6 Output: [1, _, _, 3, 3, _, 8] Process 2 (input[2]): count[2]=3, place at index 2, count[2]=2 Output: [1, _, 2, 3, 3, _, 8] Process 2 (input[1]): count[2]=2, place at index 1, count[2]=1 Output: [1, 2, 2, 3, 3, _, 8] Process 4 (input[0]): count[4]=6, place at index 5, count[4]=5 Output: [1, 2, 2, 3, 3, 4, 8] Result: [1, 2, 2, 3, 3, 4, 8] ``` #### TypeScript Implementation ```typescript function countingSort(arr: number[]): number[] { if (arr.length <= 1) return arr; const min = Math.min(...arr); const max = Math.max(...arr); const range = max - min + 1; const count = new Array(range).fill(0); const output = new Array(arr.length); for (const num of arr) { count[num - min]++; } for (let i = 1; i < range; i++) { count[i] += count[i - 1]; } for (let i = arr.length - 1; i >= 0; i--) { const pos = count[arr[i] - min] - 1; output[pos] = arr[i]; count[arr[i] - min]--; } return output; } ``` We iterate from right to left in the final step to maintain **stability**: equal elements appear in the output in the same order they appeared in the input. #### Complexity Analysis | Case | Time | Why | |---------|----------|------------------------------------------------| | Best | O(n + k) | Always counts and places | | Average | O(n + k) | Same work regardless | | Worst | O(n + k) | Same work regardless | Where **k** is the range of input values (max - min + 1). - **Space**: O(n + k) — count array of size k, output array of size n - **Stable**: Yes (with right-to-left placement) - **Adaptive**: No #### When to Use Counting Sort Counting sort is fantastic when: - Input values are **bounded integers** with a known, reasonable range - **k is O(n)** or smaller (if k is much larger than n, it becomes wasteful) - You need a **stable** linear-time sort (e.g., as a subroutine in radix sort) It falls apart when: - Values are floating-point numbers or strings - The range k is enormous relative to n (e.g., sorting 10 numbers in the range 1 to 1,000,000) --- ### Radix Sort Radix sort sorts numbers **digit by digit**, from least significant digit (LSD) to most significant digit (MSD), or vice versa. It uses a stable sort (usually counting sort) as a subroutine for each digit. The clever insight: if you sort by the ones digit first, then the tens digit, then the hundreds digit, the stability of each pass ensures the final result is fully sorted. **How it works (LSD):** 1. Find the maximum number to determine the number of digits 2. For each digit position (ones, tens, hundreds, ...): a. Sort the array by the current digit using a stable sort (counting sort) 3. After processing all digits, the array is sorted #### Visual Walkthrough Let's sort `[170, 45, 75, 90, 802, 24, 2, 66]`: ``` Original: [170, 45, 75, 90, 802, 24, 2, 66] Pass 1: Sort by ones digit 170 → 0 45 → 5 75 → 5 90 → 0 802 → 2 24 → 4 2 → 2 66 → 6 Buckets by ones: 0: [170, 90] 2: [802, 2] 4: [24] 5: [45, 75] 6: [66] After pass 1: [170, 90, 802, 2, 24, 45, 75, 66] Pass 2: Sort by tens digit 170 → 7 90 → 9 802 → 0 2 → 0 24 → 2 45 → 4 75 → 7 66 → 6 Buckets by tens: 0: [802, 2] 2: [24] 4: [45] 6: [66] 7: [170, 75] 9: [90] After pass 2: [802, 2, 24, 45, 66, 170, 75, 90] Pass 3: Sort by hundreds digit 802 → 8 2 → 0 24 → 0 45 → 0 66 → 0 170 → 1 75 → 0 90 → 0 Buckets by hundreds: 0: [2, 24, 45, 66, 75, 90] 1: [170] 8: [802] After pass 3: [2, 24, 45, 66, 75, 90, 170, 802] Result: [2, 24, 45, 66, 75, 90, 170, 802] ``` Each pass sorts by one digit, and because counting sort is stable, the ordering from previous passes is preserved. #### TypeScript Implementation ```typescript function radixSort(arr: number[]): number[] { if (arr.length <= 1) return arr; const max = Math.max(...arr); for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) { countingSortByDigit(arr, exp); } return arr; } function countingSortByDigit(arr: number[], exp: number): void { const n = arr.length; const output = new Array(n); const count = new Array(10).fill(0); for (let i = 0; i < n; i++) { const digit = Math.floor(arr[i] / exp) % 10; count[digit]++; } for (let i = 1; i < 10; i++) { count[i] += count[i - 1]; } for (let i = n - 1; i >= 0; i--) { const digit = Math.floor(arr[i] / exp) % 10; output[count[digit] - 1] = arr[i]; count[digit]--; } for (let i = 0; i < n; i++) { arr[i] = output[i]; } } ``` #### LSD vs MSD - **LSD (Least Significant Digit)**: Sorts from right to left (ones, tens, hundreds). Simpler to implement. Naturally stable. - **MSD (Most Significant Digit)**: Sorts from left to right. Can short-circuit for strings of different lengths. More complex but can be faster for variable-length keys. LSD is the standard approach for integers. MSD is more common for strings. #### Complexity Analysis | Case | Time | Why | |---------|----------|------------------------------------------------| | Best | O(d(n+k))| d passes of counting sort | | Average | O(d(n+k))| Same work regardless | | Worst | O(d(n+k))| Same work regardless | Where **d** is the number of digits and **k** is the base (10 for decimal). - **Space**: O(n + k) — output array and count array - **Stable**: Yes (uses stable counting sort) - **Adaptive**: No #### When to Use Radix Sort - **Fixed-length integers** or **strings**: When d is small relative to log(n) - **Large n with small key range**: Radix sort beats comparison sorts when d * k << n * log(n) - **Sorting strings**: MSD radix sort is the basis for many string-sorting algorithms --- ### Bucket Sort Bucket sort distributes elements into a number of **buckets**, sorts each bucket individually (usually with insertion sort), and then concatenates the results. **How it works:** 1. Create an array of empty buckets 2. Distribute elements into buckets based on some function (usually value range) 3. Sort each bucket (typically with insertion sort) 4. Concatenate all buckets in order The key insight: if elements are **uniformly distributed**, each bucket will have approximately the same number of elements, and sorting small buckets with insertion sort is fast. #### Visual Walkthrough Let's sort `[0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]` using 5 buckets: ``` Input: [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68] Distribute into 5 buckets (bucket = floor(value * 5)): Bucket 0 [0.00-0.20): [0.17, 0.12] Bucket 1 [0.20-0.40): [0.39, 0.26, 0.21, 0.23] Bucket 2 [0.40-0.60): [] Bucket 3 [0.60-0.80): [0.78, 0.72, 0.68] Bucket 4 [0.80-1.00): [0.94] Sort each bucket (insertion sort): Bucket 0: [0.12, 0.17] Bucket 1: [0.21, 0.23, 0.26, 0.39] Bucket 2: [] Bucket 3: [0.68, 0.72, 0.78] Bucket 4: [0.94] Concatenate: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94] ``` #### TypeScript Implementation ```typescript function bucketSort(arr: number[], bucketCount = 5): number[] { if (arr.length <= 1) return arr; const min = Math.min(...arr); const max = Math.max(...arr); if (min === max) return arr; const range = max - min; const buckets: number[][] = Array.from({ length: bucketCount }, () => []); for (const num of arr) { const bucketIndex = Math.min( Math.floor(((num - min) / range) * (bucketCount - 1)), bucketCount - 1 ); buckets[bucketIndex].push(num); } for (const bucket of buckets) { insertionSortBucket(bucket); } let index = 0; for (const bucket of buckets) { for (const num of bucket) { arr[index++] = num; } } return arr; } function insertionSortBucket(arr: number[]): void { for (let i = 1; i < arr.length; i++) { const key = arr[i]; let j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } } ``` #### Complexity Analysis | Case | Time | Why | |---------|----------|--------------------------------------------------| | Best | O(n + k) | Uniform distribution, tiny buckets | | Average | O(n + k) | With uniform distribution and k ≈ n buckets | | Worst | O(n²) | All elements in one bucket, degrades to insertion | Where **k** is the number of buckets. - **Space**: O(n + k) — buckets and their contents - **Stable**: Yes (if the bucket sort used is stable) - **Adaptive**: Depends on the sub-sort #### When to Use Bucket Sort - **Uniformly distributed** floating-point numbers in a known range - **Hash-based distribution**: When you can design a good hash function to distribute elements evenly - When combined with a good sub-sort (insertion sort for small buckets) Bucket sort degrades badly when the distribution is skewed (all elements end up in one bucket). It's best used when you have prior knowledge about the data distribution. --- ## The Master Comparison Table Here's every algorithm side by side. Pin this table to your wall. | Algorithm | Best | Average | Worst | Space | Stable | In-Place | Adaptive | Best Use Case | |----------------|-------------|-------------|-------------|---------|--------|----------|----------|--------------------------------------| | Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes | Yes | Teaching, nearly sorted data | | Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Yes | No | Minimizing swaps | | Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes | Yes | Small arrays, nearly sorted data | | Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No | No | Stability needed, linked lists | | Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n)| No | Yes | No | General-purpose, cache-friendly | | Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes | No | Guaranteed O(n log n) + O(1) space | | Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(n+k) | Yes | No | No | Bounded integers, small range | | Radix Sort | O(d(n + k)) | O(d(n + k)) | O(d(n + k)) | O(n+k) | Yes | No | No | Fixed-width integers/strings | | Bucket Sort | O(n + k) | O(n + k) | O(n²) | O(n+k) | Yes | No | No | Uniform distribution, known range | > **Quick reference**: Need stable? Merge sort. Need in-place + guaranteed time? Heap sort. Need fastest average? Quick sort. Bounded integers? Counting sort. --- ## When to Use Which: The Decision Framework Choosing the right sorting algorithm isn't about memorizing which is “best”. It's about understanding your **constraints** and **data characteristics**. Here's a decision framework: ``` ┌─────────────────────────┐ │ What are you sorting? │ └────────────┬────────────┘ │ ┌────────────▼────────────┐ │ Bounded integers with │ YES │ small range (k ≈ n)? │ NO ┌─────┤ ├─────┐ │ └─────────────────────────┘ │ ▼ ▼ ┌────────────────┐ ┌───────────────────┐ │ Counting Sort │ │ How large is the │ │ or Radix Sort │ │ input? │ └────────────────┘ └─────────┬─────────┘ │ ┌──────────────┼──────────────┐ ▼ ▼ ▼ Small (n<50) Medium/Large Huge/External │ │ │ ▼ ▼ ▼ ┌──────────┐ ┌──────────────┐ ┌──────────┐ │Insertion │ │Nearly sorted?│ │Merge Sort│ │ Sort │ └──────┬───────┘ │(external)│ └──────────┘ │ └──────────┘ YES │ NO ┌───────┼───────┐ ▼ ▼ ┌──────────┐ ┌──────────────┐ │Insertion │ │Need stability?│ │ Sort │ └──────┬───────┘ └──────────┘ │ YES │ NO ┌───────┼───────┐ ▼ ▼ ┌──────────┐ ┌──────────────┐ │Merge Sort│ │Memory tight? │ │or TimSort│ └──────┬───────┘ └──────────┘ │ YES │ NO ┌───────┼───────┐ ▼ ▼ ┌────────────┐ ┌──────────┐ │Quick Sort │ │Quick Sort│ │or Heap Sort│ │ │ └────────────┘ └──────────┘ ``` ### Quick Decision Rules | Situation | Best Choice | |------------------------------------|----------------------------------------------| | Small array (n < 50) | Insertion sort | | Nearly sorted data | Insertion sort or TimSort | | Need stability | Merge sort or TimSort | | Memory constrained | Quick sort (avg) or heap sort (guaranteed) | | Bounded integers, small range | Counting sort | | Fixed-width integer keys | Radix sort | | Uniformly distributed floats | Bucket sort | | General purpose | Quick sort or TimSort | | Guaranteed worst case + low memory | Heap sort | | Linked list | Merge sort | | External sorting (disk) | Merge sort (k-way merge) | | Parallel sorting | Merge sort (naturally parallelizable) | --- ## Sorting in Practice: What Real Languages Use Sorting in the real world is never a pure textbook algorithm. Every production implementation is a **hybrid** that combines the strengths of multiple algorithms. ### V8 Engine (JavaScript / Node.js) — TimSort Since 2019, V8 uses **TimSort** for `Array.prototype.sort()`. Before that, it used QuickSort for arrays longer than 10 elements and insertion sort for smaller ones. TimSort's key features: - Identifies naturally occurring sorted **runs** in the data - Extends short runs to a minimum length (typically 32-64) using **insertion sort** - Merges runs using a modified **merge sort** with a merge stack that ensures balanced merging - Adaptive: O(n) on already-sorted data, O(n log n) worst case - Stable ### Python — TimSort Python was the birthplace of TimSort (2002). `list.sort()` and `sorted()` both use it. Tim Peters designed it specifically for real-world data, which tends to have existing patterns (partially sorted, runs of ascending/descending values). ### Java — Dual-Pivot QuickSort + TimSort Java uses **two different algorithms**: - `Arrays.sort()` for primitives: **Dual-Pivot QuickSort** (Vladimir Yaroslavskiy, 2009). Uses two pivots instead of one, creating three partitions. Faster than traditional single-pivot quicksort in practice. - `Arrays.sort()` for objects: **TimSort** (because stability is required for objects) ### C++ — Introsort `std::sort` uses **Introsort** (introspective sort): 1. Start with **quick sort** (fast average case) 2. If recursion depth exceeds 2 * log₂(n), switch to **heap sort** (guaranteed O(n log n)) 3. For small subarrays (typically < 16), switch to **insertion sort** This gives you quick sort's speed, heap sort's worst-case guarantee, and insertion sort's small-array efficiency. ### Go — Pattern-Defeating QuickSort (pdqsort) Go's `sort.Sort` uses **pdqsort**, a sophisticated variant of quicksort that: - Falls back to heap sort on degenerate cases - Uses insertion sort for small slices - Detects and handles patterns like already-sorted, reverse-sorted, and many duplicates - Achieves O(n) on common patterns while maintaining O(n log n) worst case ### The Lesson Every major language uses a **hybrid** approach. The textbook algorithms are building blocks; the real art is combining them intelligently based on input characteristics. --- ## Sorting-Related Interview Patterns Sorting shows up constantly in interviews, often as a preprocessing step or a core technique within a larger problem. Here are the most common patterns. ### Sort Colors / Dutch National Flag (3-Way Partition) **Problem**: Given an array with only 0s, 1s, and 2s, sort it in-place in a single pass. This is essentially a 3-way partition, the same idea behind handling duplicates in quicksort. You maintain three pointers: ```typescript function sortColors(nums: number[]): void { let low = 0; let mid = 0; let high = nums.length - 1; while (mid <= high) { if (nums[mid] === 0) { [nums[low], nums[mid]] = [nums[mid], nums[low]]; low++; mid++; } else if (nums[mid] === 1) { mid++; } else { [nums[mid], nums[high]] = [nums[high], nums[mid]]; high--; } } } ``` ``` Walkthrough with [2, 0, 2, 1, 1, 0]: low=0, mid=0, high=5 [2, 0, 2, 1, 1, 0] nums[mid]=2, swap with high ^ ^ [0, 0, 2, 1, 1, 2] high-- ^ ^ low=0, mid=0, high=4 [0, 0, 2, 1, 1, 2] nums[mid]=0, swap with low ^ low=1, mid=1, high=4 [0, 0, 2, 1, 1, 2] nums[mid]=0, swap with low ^ low=2, mid=2, high=4 [0, 0, 2, 1, 1, 2] nums[mid]=2, swap with high ^ ^ [0, 0, 1, 1, 2, 2] high-- ^ ^ low=2, mid=2, high=3 [0, 0, 1, 1, 2, 2] nums[mid]=1, mid++ ^ ^ low=2, mid=3, high=3 [0, 0, 1, 1, 2, 2] nums[mid]=1, mid++ ^ mid > high → done! Result: [0, 0, 1, 1, 2, 2] ``` **Key insight**: This is O(n) time, O(1) space, single pass. The 3-way partition is also the basis for handling duplicate pivots efficiently in quicksort. --- ### Merge Intervals **Problem**: Given a collection of intervals, merge all overlapping intervals. The trick: **sort by start time first**, then merge in a single pass. ```typescript function mergeIntervals(intervals: number[][]): number[][] { if (intervals.length <= 1) return intervals; intervals.sort((a, b) => a[0] - b[0]); const merged: number[][] = [intervals[0]]; for (let i = 1; i < intervals.length; i++) { const current = intervals[i]; const lastMerged = merged[merged.length - 1]; if (current[0] <= lastMerged[1]) { lastMerged[1] = Math.max(lastMerged[1], current[1]); } else { merged.push(current); } } return merged; } ``` ``` Example: [[1,3], [2,6], [8,10], [15,18]] After sorting by start: [[1,3], [2,6], [8,10], [15,18]] (already sorted) Process [1,3]: merged = [[1,3]] Process [2,6]: 2 ≤ 3 → overlap! merged = [[1,6]] Process [8,10]: 8 > 6 → no overlap. merged = [[1,6], [8,10]] Process [15,18]: 15 > 10 → no overlap. merged = [[1,6], [8,10], [15,18]] Result: [[1,6], [8,10], [15,18]] ``` **Key insight**: Sorting transforms a complex overlap-detection problem into a simple linear scan. O(n log n) overall. --- ### Other Common Interview Patterns **Meeting Rooms**: Sort intervals by start time, then check for any overlap. If any interval starts before the previous one ends, meetings conflict. **K Closest Points to Origin**: You don't need a full sort. Use **quickselect** (partition-based selection) for O(n) average time, or a **min-heap** of size k for O(n log k). **Custom Sort Order**: Use a comparator to define custom ordering. For example, arranging numbers to form the largest possible number: ```typescript function largestNumber(nums: number[]): string { const result = nums .map(String) .sort((a, b) => (b + a).localeCompare(a + b)) .join(''); return result[0] === '0' ? '0' : result; } ``` **Top K Frequent Elements**: Count frequencies with a hash map, then use a sort or a heap to find the top k. --- ## Common Pitfalls These are the mistakes that trip people up most often with sorting. ### 1. The Comparator Bug ```typescript // WRONG: doesn't handle all cases properly numbers.sort((a, b) => a > b ? 1 : -1); // RIGHT: handles equal elements too numbers.sort((a, b) => a - b); ``` The first version never returns 0, which means equal elements might get unnecessarily rearranged (breaking stability) and can even cause incorrect results in some edge cases. For non-numeric types, always return -1, 0, or 1: ```typescript strings.sort((a, b) => a.localeCompare(b)); ``` ### 2. Assuming `.sort()` Is Stable Before ES2019, the JavaScript spec didn't guarantee stability. While modern engines (V8, SpiderMonkey, JavaScriptCore) all use stable sorts now, if you're targeting older environments, you might need a polyfill or a manual stable sort. ### 3. Quicksort's O(n²) Trap If you implement quicksort with first or last element as pivot on already-sorted data, you get O(n²). This is a classic interview pitfall. Always use **random pivot** or **median-of-three**. ```typescript // BAD: O(n²) on sorted input const pivot = arr[hi]; // GOOD: O(n²) becomes astronomically unlikely const randomIndex = lo + Math.floor(Math.random() * (hi - lo + 1)); [arr[randomIndex], arr[hi]] = [arr[hi], arr[randomIndex]]; const pivot = arr[hi]; ``` ### 4. Counting Sort on Unbounded Data Counting sort needs O(k) space where k is the range of values. If you try to counting-sort an array like `[1, 1000000000]`, you'll allocate a billion-element array. Always check the range before choosing counting sort. ### 5. Forgetting That Sorts Modify the Original Array In JavaScript, `.sort()` mutates the array in place AND returns it. This catches people off guard: ```typescript const original = [3, 1, 2]; const sorted = original.sort((a, b) => a - b); console.log(original); // [1, 2, 3] ← mutated! console.log(sorted === original); // true ← same reference! ``` If you need to preserve the original: ```typescript const sorted = [...original].sort((a, b) => a - b); // or const sorted = original.toSorted((a, b) => a - b); // ES2023+ ``` ### 6. Sorting Objects Without a Proper Comparator ```typescript const users = [ { name: 'Charlie', age: 30 }, { name: 'Alice', age: 25 }, { name: 'Bob', age: 30 }, ]; // WRONG: converts objects to "[object Object]" strings users.sort(); // RIGHT: compare by specific field users.sort((a, b) => a.age - b.age); // Multi-key sort: age first, then name users.sort((a, b) => { if (a.age !== b.age) return a.age - b.age; return a.name.localeCompare(b.name); }); ``` --- ## Cheat Sheet ### Algorithm Quick Reference ``` ┌────────────────┬────────────┬────────────┬────────────┬─────────┬────────┐ │ Algorithm │ Best │ Average │ Worst │ Space │ Stable │ ├────────────────┼────────────┼────────────┼────────────┼─────────┼────────┤ │ Bubble Sort │ O(n) │ O(n²) │ O(n²) │ O(1) │ Yes │ │ Selection Sort │ O(n²) │ O(n²) │ O(n²) │ O(1) │ No │ │ Insertion Sort │ O(n) │ O(n²) │ O(n²) │ O(1) │ Yes │ │ Merge Sort │ O(n log n) │ O(n log n) │ O(n log n) │ O(n) │ Yes │ │ Quick Sort │ O(n log n) │ O(n log n) │ O(n²) │O(log n) │ No │ │ Heap Sort │ O(n log n) │ O(n log n) │ O(n log n) │ O(1) │ No │ │ Counting Sort │ O(n + k) │ O(n + k) │ O(n + k) │O(n + k) │ Yes │ │ Radix Sort │ O(d(n+k)) │ O(d(n+k)) │ O(d(n+k)) │O(n + k) │ Yes │ │ Bucket Sort │ O(n + k) │ O(n + k) │ O(n²) │O(n + k) │ Yes │ └────────────────┴────────────┴────────────┴────────────┴─────────┴────────┘ ``` ### Decision Tree (Text Version) 1. **Are the values bounded integers with a small range?** - Yes → **Counting sort** (or radix sort for multi-digit keys) 2. **Is the array small (n < ~50)?** - Yes → **Insertion sort** 3. **Is the data nearly sorted?** - Yes → **Insertion sort** or **TimSort** 4. **Do you need stability?** - Yes → **Merge sort** or **TimSort** 5. **Is memory tight?** - Yes → **Quick sort** (average O(n log n)) or **Heap sort** (guaranteed) 6. **General purpose?** - → **Quick sort** (fastest average) or **TimSort** (stable + adaptive) ### Stability Quick Reference **Stable sorts** (preserve order of equal elements): - Bubble sort, Insertion sort, Merge sort, Counting sort, Radix sort, Bucket sort, TimSort **Unstable sorts** (may reorder equal elements): - Selection sort, Quick sort, Heap sort ### The Golden Rules 1. **Know your data**: The best algorithm depends on what you're sorting, how much of it there is, and what it looks like 2. **Don't reinvent the wheel**: Use your language's built-in sort for 99% of cases. It's battle-tested and optimized 3. **Understand the trade-offs**: There's no universally “best” sort. Every algorithm sacrifices something 4. **Stability matters more than you think**: When sorting objects or doing multi-pass sorts, stability prevents subtle bugs 5. **The O(n log n) barrier is real**: For comparison-based sorting, you cannot beat it. But non-comparison sorts can, if the data allows --- ## Wrapping Up Sorting algorithms are so much more than a textbook exercise. They're a lens through which you can understand fundamental ideas in computer science: - **Divide and conquer** (merge sort, quick sort) - **Greedy selection** (selection sort) - **Heap data structures** (heap sort) - **Counting and hashing** (counting sort, bucket sort) - **Digit-by-digit processing** (radix sort) - **Adaptivity and hybrid design** (TimSort, introsort) - **Trade-off analysis** (time vs. space, stability vs. speed, worst case vs. average case) Every time you call `.sort()` in your code, an extraordinary amount of engineering and theory is working behind the scenes. TimSort didn't come from nowhere. It came from decades of studying exactly the algorithms we've covered here, understanding their strengths and weaknesses, and combining them into something greater than the sum of its parts. Whether you're preparing for interviews, building performance-critical applications, or just want to deeply understand how computers work, mastering sorting algorithms is one of the best investments you can make. Now go sort something.

Sorting Algorithms: The Complete Deep Dive