> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.

# Sorting Algorithms

> Master essential sorting techniques and their applications

<img className="block rounded-lg" src="https://mintcdn.com/devweeekends/8SzFxu49daVetHjN/images/dsa-techniques/20-sorting.svg?fit=max&auto=format&n=8SzFxu49daVetHjN&q=85&s=7e6d2d57e358f3b4c26103998fdb5315" alt="Sorting Algorithms" width="1080" height="1080" data-path="images/dsa-techniques/20-sorting.svg" />

## Overview

**Sorting** arranges elements in a specific order (typically ascending). While most languages provide a built-in sort (Timsort in Python and Java, Introsort in C++), understanding the underlying algorithms is essential for interviews because: (1) you may be asked to implement them, (2) several important patterns (merge intervals, meeting rooms, custom comparators) depend on sorted input, and (3) questions like "Kth Largest Element" require knowing how Quick Select works under the hood.

**A senior engineer's perspective:** In production code, you almost never write your own sort -- you use the standard library. But knowing the algorithms lets you make informed choices (stable vs unstable, in-place vs out-of-place, worst-case guarantees) and recognize when a problem can be solved by *sorting first* as a preprocessing step.

## Pattern Recognition Cheatsheet

<Tip>
  **If you see one of these phrases in a LeetCode problem, sorting (or partial sorting) is almost certainly part of the solution.**

  | Problem Keyword                                         | Technique                                                                 | Template to Reach For                         |
  | ------------------------------------------------------- | ------------------------------------------------------------------------- | --------------------------------------------- |
  | "kth largest", "kth smallest", "top K elements"         | Quick Select OR min/max heap of size K                                    | Partition-based selection or heap             |
  | "merge intervals", "overlapping ranges", "consolidate"  | Sort by start time, then linear scan                                      | Sort + greedy merge                           |
  | "schedule meetings", "minimum conference rooms"         | Sort starts and ends separately, or sort by start + min-heap of end times | Sort + heap or two-pointer sweep              |
  | "custom ordering", "sort by frequency", "lexicographic" | Built-in sort with key/comparator                                         | `sorted(arr, key=...)` or comparator function |
  | "sort 0s, 1s, 2s in one pass", "Dutch flag"             | Three-way partition with low/mid/high                                     | In-place with three pointers                  |
  | "sort almost-sorted array", "K-sorted"                  | Min-heap of size K+1                                                      | Heap of bounded size                          |
  | "find the median", "running median"                     | Two heaps (max-heap of lower half, min-heap of upper half)                | Balanced two-heap                             |
  | "anagram groups", "find duplicates"                     | Sort each string as a canonical key                                       | Sort + HashMap by key                         |
  | "smallest range covering K lists"                       | Min-heap of one element per list                                          | K-way merge structure                         |
  | "wiggle sort", "sort half then interleave"              | Sort + two-pointer placement                                              | Sort first, place from ends inward            |

  **Rule of thumb**: if the problem involves comparing elements pairwise or finding extrema, ask yourself "would this be easier if the input were sorted?" If yes, the O(n log n) sort cost is almost always worth it -- and library `sort()` is your friend.
</Tip>

## Universal Templates

These templates show you the canonical implementations interviewers expect to see, plus the language built-ins that you should reach for in production. Memorize the structure of quicksort and mergesort cold; for everything else, lean on the standard library.

<CodeGroup>
  ```python Python theme={null}
  # TEMPLATE 1: Quicksort (in-place, O(n log n) average, O(n^2) worst)
  def quicksort(arr, lo=0, hi=None):
      if hi is None:
          hi = len(arr) - 1
      if lo < hi:
          p = partition(arr, lo, hi)
          quicksort(arr, lo, p - 1)
          quicksort(arr, p + 1, hi)

  def partition(arr, lo, hi):
      pivot = arr[hi]
      i = lo - 1
      for j in range(lo, hi):
          if arr[j] <= pivot:
              i += 1
              arr[i], arr[j] = arr[j], arr[i]
      arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
      return i + 1

  # TEMPLATE 2: Mergesort (stable, O(n log n) guaranteed, O(n) extra space)
  def mergesort(arr):
      if len(arr) <= 1:
          return arr
      mid = len(arr) // 2
      left = mergesort(arr[:mid])
      right = mergesort(arr[mid:])
      return merge(left, right)

  def merge(a, b):
      result, i, j = [], 0, 0
      while i < len(a) and j < len(b):
          if a[i] <= b[j]:           # <= preserves stability
              result.append(a[i]); i += 1
          else:
              result.append(b[j]); j += 1
      result.extend(a[i:])
      result.extend(b[j:])
      return result

  # TEMPLATE 3: Custom comparator (LeetCode 179, 937, etc.)
  from functools import cmp_to_key
  # Sort by key (preferred -- stable, O(n log n))
  sorted(arr, key=lambda x: (x.priority, x.name))
  # Sort by full pairwise comparator (slower -- use only when key trick is infeasible)
  def compare(a, b):
      return -1 if a + b > b + a else 1     # for "Largest Number" problem
  sorted(arr, key=cmp_to_key(compare))
  ```

  ```java Java theme={null}
  // TEMPLATE 1: Quicksort
  void quicksort(int[] a, int lo, int hi) {
      if (lo < hi) {
          int p = partition(a, lo, hi);
          quicksort(a, lo, p - 1);
          quicksort(a, p + 1, hi);
      }
  }
  int partition(int[] a, int lo, int hi) {
      int pivot = a[hi], i = lo - 1;
      for (int j = lo; j < hi; j++) {
          if (a[j] <= pivot) {
              i++;
              int t = a[i]; a[i] = a[j]; a[j] = t;
          }
      }
      int t = a[i + 1]; a[i + 1] = a[hi]; a[hi] = t;
      return i + 1;
  }

  // TEMPLATE 2: Mergesort -- mostly written in interviews; in production use Arrays.sort()

  // TEMPLATE 3: Custom comparator
  // Returns negative if a should come before b, positive if after, zero if equal.
  // MUST be transitive and consistent.
  Arrays.sort(arr, (a, b) -> a.priority - b.priority);   // careful: subtraction can overflow
  Arrays.sort(arr, Comparator.comparingInt(x -> x.priority));   // safer
  ```

  ```javascript JavaScript theme={null}
  // TEMPLATE 1: Quicksort -- usually not implemented; V8 engine uses Timsort

  // TEMPLATE 2: Mergesort -- same -- use built-in

  // TEMPLATE 3: Custom comparator
  // Comparator returns negative, zero, or positive -- NOT a boolean
  arr.sort((a, b) => a.priority - b.priority);          // ascending by priority
  arr.sort((a, b) => b.priority - a.priority);          // descending
  // For string concatenation comparison (LC 179)
  arr.sort((a, b) => (b + a).localeCompare(a + b));
  ```

  ```cpp C++ theme={null}
  // TEMPLATE 1: Quicksort -- std::sort uses Introsort (quicksort + heapsort fallback)
  std::sort(arr.begin(), arr.end());

  // TEMPLATE 2: Mergesort -- std::stable_sort is mergesort
  std::stable_sort(arr.begin(), arr.end());

  // TEMPLATE 3: Custom comparator
  // Returns true if a should come BEFORE b (strict weak ordering)
  std::sort(arr.begin(), arr.end(), [](const T& a, const T& b) {
      return a.priority < b.priority;
  });
  ```
</CodeGroup>

<Warning>
  **Caveats and Traps -- internalize these before any sorting interview.**

  1. **Stable vs unstable matters when ties have meaning.** If you sort employees by department and equal-department employees should stay in their original alphabetical order, you need a stable sort. Python's `sorted()` and Java's `Collections.sort()` are stable. Quicksort and heapsort are unstable. Mistake: sorting by a single key when the input was already partially sorted by a secondary key, expecting that secondary order to be preserved with an unstable sort.
  2. **Comparator must be transitive -- return -1/0/1, not a boolean.** A comparator that violates transitivity (returns inconsistent results for the same pair) causes undefined behavior, IllegalArgumentException in Java, or sometimes silent corruption. The classic bug: `return a - b` when a and b can be near INT\_MIN/INT\_MAX -- the subtraction overflows. Always use `Integer.compare(a, b)` in Java or explicit if/else in any language.
  3. **Python `sort` with `key` is stable AND fast; `cmp_to_key` is slow.** Prefer `sorted(arr, key=lambda x: (x.priority, x.name))` over `cmp_to_key`. The key version is O(n log n) with cheap comparisons; cmp\_to\_key wraps every value in a comparison object and is 2-3x slower in practice.
  4. **Quicksort's worst case is O(n^2) on already-sorted input with last-element pivot.** This is why production quicksorts (Java, Rust, std::sort) use median-of-three or randomized pivots, and why std::sort falls back to heapsort if recursion depth gets too large (Introsort).
  5. **Counting sort fails on large ranges.** It is O(n + k) where k is the range. Sorting 100 integers in \[0, 10^9] is a billion-cell allocation -- catastrophic. Counting sort wins only when k = O(n) or smaller.
  6. **Dutch flag pivots break naive Lomuto partition with many duplicates.** If most elements equal the pivot, all elements go to one side and quicksort degenerates to O(n^2). Use three-way (Dutch flag) partitioning when duplicates are common.
</Warning>

## When to Choose Which

<CardGroup cols={2}>
  <Card title="Quick Sort" icon="bolt">
    General purpose, in-place, average O(n log n)
  </Card>

  <Card title="Merge Sort" icon="code-merge">
    Stable, guaranteed O(n log n), linked lists
  </Card>

  <Card title="Heap Sort" icon="mountain">
    In-place, O(n log n), no extra memory
  </Card>

  <Card title="Counting Sort" icon="calculator">
    Linear time for small range integers
  </Card>
</CardGroup>

## Algorithm Implementations

### 1. Quick Sort

<CodeGroup>
  ```python Python theme={null}
  def quick_sort(arr, low=0, high=None):
      """Average O(n log n), in-place, unstable"""
      if high is None:
          high = len(arr) - 1
      
      if low < high:
          pivot_idx = partition(arr, low, high)
          quick_sort(arr, low, pivot_idx - 1)
          quick_sort(arr, pivot_idx + 1, high)
      
      return arr

  def partition(arr, low, high):
      pivot = arr[high]
      i = low - 1
      
      for j in range(low, high):
          if arr[j] < pivot:
              i += 1
              arr[i], arr[j] = arr[j], arr[i]
      
      arr[i + 1], arr[high] = arr[high], arr[i + 1]
      return i + 1
  ```

  ```java Java theme={null}
  public class QuickSort {
      public void quickSort(int[] arr, int low, int high) {
          // Average O(n log n), in-place, unstable
          if (low < high) {
              int pivotIdx = partition(arr, low, high);
              quickSort(arr, low, pivotIdx - 1);
              quickSort(arr, pivotIdx + 1, high);
          }
      }
      
      private int partition(int[] arr, int low, int high) {
          int pivot = arr[high];
          int i = low - 1;
          
          for (int j = low; j < high; j++) {
              if (arr[j] < pivot) {
                  i++;
                  swap(arr, i, j);
              }
          }
          
          swap(arr, i + 1, high);
          return i + 1;
      }
      
      private void swap(int[] arr, int i, int j) {
          int temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
      }
  }
  ```

  ```cpp C++ theme={null}
  class QuickSort {
  public:
      void quickSort(vector<int>& arr, int low, int high) {
          // Average O(n log n), in-place, unstable
          if (low < high) {
              int pivotIdx = partition(arr, low, high);
              quickSort(arr, low, pivotIdx - 1);
              quickSort(arr, pivotIdx + 1, high);
          }
      }
      
  private:
      int partition(vector<int>& arr, int low, int high) {
          int pivot = arr[high];
          int i = low - 1;
          
          for (int j = low; j < high; j++) {
              if (arr[j] < pivot) {
                  i++;
                  swap(arr[i], arr[j]);
              }
          }
          
          swap(arr[i + 1], arr[high]);
          return i + 1;
      }
  };
  ```
</CodeGroup>

### 2. Merge Sort

<CodeGroup>
  ```python Python theme={null}
  def merge_sort(arr):
      """O(n log n), stable, O(n) space"""
      if len(arr) <= 1:
          return arr
      
      mid = len(arr) // 2
      left = merge_sort(arr[:mid])
      right = merge_sort(arr[mid:])
      
      return merge(left, right)

  def merge(left, right):
      result = []
      i = j = 0
      
      while i < len(left) and j < len(right):
          if left[i] <= right[j]:
              result.append(left[i])
              i += 1
          else:
              result.append(right[j])
              j += 1
      
      result.extend(left[i:])
      result.extend(right[j:])
      return result
  ```

  ```java Java theme={null}
  public class MergeSort {
      public int[] mergeSort(int[] arr) {
          // O(n log n), stable, O(n) space
          if (arr.length <= 1) {
              return arr;
          }
          
          int mid = arr.length / 2;
          int[] left = mergeSort(Arrays.copyOfRange(arr, 0, mid));
          int[] right = mergeSort(Arrays.copyOfRange(arr, mid, arr.length));
          
          return merge(left, right);
      }
      
      private int[] merge(int[] left, int[] right) {
          int[] result = new int[left.length + right.length];
          int i = 0, j = 0, k = 0;
          
          while (i < left.length && j < right.length) {
              if (left[i] <= right[j]) {
                  result[k++] = left[i++];
              } else {
                  result[k++] = right[j++];
              }
          }
          
          while (i < left.length) result[k++] = left[i++];
          while (j < right.length) result[k++] = right[j++];
          
          return result;
      }
  }
  ```

  ```cpp C++ theme={null}
  class MergeSort {
  public:
      vector<int> mergeSort(vector<int>& arr) {
          // O(n log n), stable, O(n) space
          if (arr.size() <= 1) {
              return arr;
          }
          
          int mid = arr.size() / 2;
          vector<int> left(arr.begin(), arr.begin() + mid);
          vector<int> right(arr.begin() + mid, arr.end());
          
          left = mergeSort(left);
          right = mergeSort(right);
          
          return merge(left, right);
      }
      
  private:
      vector<int> merge(vector<int>& left, vector<int>& right) {
          vector<int> result;
          int i = 0, j = 0;
          
          while (i < left.size() && j < right.size()) {
              if (left[i] <= right[j]) {
                  result.push_back(left[i++]);
              } else {
                  result.push_back(right[j++]);
              }
          }
          
          while (i < left.size()) result.push_back(left[i++]);
          while (j < right.size()) result.push_back(right[j++]);
          
          return result;
      }
  };
  ```
</CodeGroup>

### 3. Heap Sort

<CodeGroup>
  ```python Python theme={null}
  def heap_sort(arr):
      """O(n log n), in-place, unstable"""
      n = len(arr)
      
      # Build max heap
      for i in range(n // 2 - 1, -1, -1):
          heapify(arr, n, i)
      
      # Extract elements
      for i in range(n - 1, 0, -1):
          arr[0], arr[i] = arr[i], arr[0]
          heapify(arr, i, 0)
      
      return arr

  def heapify(arr, n, i):
      largest = i
      left = 2 * i + 1
      right = 2 * i + 2
      
      if left < n and arr[left] > arr[largest]:
          largest = left
      if right < n and arr[right] > arr[largest]:
          largest = right
      
      if largest != i:
          arr[i], arr[largest] = arr[largest], arr[i]
          heapify(arr, n, largest)
  ```

  ```java Java theme={null}
  public class HeapSort {
      public void heapSort(int[] arr) {
          // O(n log n), in-place, unstable
          int n = arr.length;
          
          // Build max heap
          for (int i = n / 2 - 1; i >= 0; i--) {
              heapify(arr, n, i);
          }
          
          // Extract elements
          for (int i = n - 1; i > 0; i--) {
              swap(arr, 0, i);
              heapify(arr, i, 0);
          }
      }
      
      private void heapify(int[] arr, int n, int i) {
          int largest = i;
          int left = 2 * i + 1;
          int right = 2 * i + 2;
          
          if (left < n && arr[left] > arr[largest]) {
              largest = left;
          }
          if (right < n && arr[right] > arr[largest]) {
              largest = right;
          }
          
          if (largest != i) {
              swap(arr, i, largest);
              heapify(arr, n, largest);
          }
      }
      
      private void swap(int[] arr, int i, int j) {
          int temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
      }
  }
  ```

  ```cpp C++ theme={null}
  class HeapSort {
  public:
      void heapSort(vector<int>& arr) {
          // O(n log n), in-place, unstable
          int n = arr.size();
          
          // Build max heap
          for (int i = n / 2 - 1; i >= 0; i--) {
              heapify(arr, n, i);
          }
          
          // Extract elements
          for (int i = n - 1; i > 0; i--) {
              swap(arr[0], arr[i]);
              heapify(arr, i, 0);
          }
      }
      
  private:
      void heapify(vector<int>& arr, int n, int i) {
          int largest = i;
          int left = 2 * i + 1;
          int right = 2 * i + 2;
          
          if (left < n && arr[left] > arr[largest]) {
              largest = left;
          }
          if (right < n && arr[right] > arr[largest]) {
              largest = right;
          }
          
          if (largest != i) {
              swap(arr[i], arr[largest]);
              heapify(arr, n, largest);
          }
      }
  };
  ```
</CodeGroup>

### 4. Counting Sort

<CodeGroup>
  ```python Python theme={null}
  def counting_sort(arr):
      """O(n + k), stable, for small range integers"""
      if not arr:
          return arr
      
      min_val, max_val = min(arr), max(arr)
      range_size = max_val - min_val + 1
      
      count = [0] * range_size
      output = [0] * len(arr)
      
      # Count occurrences
      for num in arr:
          count[num - min_val] += 1
      
      # Cumulative count
      for i in range(1, range_size):
          count[i] += count[i - 1]
      
      # Build output (reverse for stability)
      for num in reversed(arr):
          output[count[num - min_val] - 1] = num
          count[num - min_val] -= 1
      
      return output
  ```

  ```java Java theme={null}
  public class CountingSort {
      public int[] countingSort(int[] arr) {
          // O(n + k), stable, for small range integers
          if (arr.length == 0) return arr;
          
          int minVal = Arrays.stream(arr).min().getAsInt();
          int maxVal = Arrays.stream(arr).max().getAsInt();
          int rangeSize = maxVal - minVal + 1;
          
          int[] count = new int[rangeSize];
          int[] output = new int[arr.length];
          
          // Count occurrences
          for (int num : arr) {
              count[num - minVal]++;
          }
          
          // Cumulative count
          for (int i = 1; i < rangeSize; i++) {
              count[i] += count[i - 1];
          }
          
          // Build output (reverse for stability)
          for (int i = arr.length - 1; i >= 0; i--) {
              output[count[arr[i] - minVal] - 1] = arr[i];
              count[arr[i] - minVal]--;
          }
          
          return output;
      }
  }
  ```

  ```cpp C++ theme={null}
  class CountingSort {
  public:
      vector<int> countingSort(vector<int>& arr) {
          // O(n + k), stable, for small range integers
          if (arr.empty()) return arr;
          
          int minVal = *min_element(arr.begin(), arr.end());
          int maxVal = *max_element(arr.begin(), arr.end());
          int rangeSize = maxVal - minVal + 1;
          
          vector<int> count(rangeSize, 0);
          vector<int> output(arr.size());
          
          // Count occurrences
          for (int num : arr) {
              count[num - minVal]++;
          }
          
          // Cumulative count
          for (int i = 1; i < rangeSize; i++) {
              count[i] += count[i - 1];
          }
          
          // Build output (reverse for stability)
          for (int i = arr.size() - 1; i >= 0; i--) {
              output[count[arr[i] - minVal] - 1] = arr[i];
              count[arr[i] - minVal]--;
          }
          
          return output;
      }
  };
  ```
</CodeGroup>

## Complexity Comparison

| Algorithm     | Best       | Average    | Worst      | Space    | Stable |
| ------------- | ---------- | ---------- | ---------- | -------- | ------ |
| Quick Sort    | O(n log n) | O(n log n) | O(n^2)     | O(log n) | No     |
| Merge Sort    | O(n log n) | O(n log n) | O(n log n) | O(n)     | Yes    |
| 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(k)     | Yes    |

## Worked LeetCode Problems

These problems cover the four most-asked sorting patterns at FAANG: kth-element selection, interval merging, scheduling, and Dutch flag partitioning. Drill these to instinct.

### LC 215 -- Kth Largest Element in an Array (Medium)

**Brute force**: sort the entire array descending and return `arr[k-1]`. O(n log n) time, O(1) space if in-place sort.

**Optimized A -- min-heap of size K**: maintain a min-heap of K elements; the root is always the kth largest. O(n log k) time, O(k) space. Better when k is much smaller than n.

```python theme={null}
import heapq
def findKthLargest(nums, k):
    heap = []
    for n in nums:
        heapq.heappush(heap, n)
        if len(heap) > k:
            heapq.heappop(heap)        # discard smallest -- keep top K
    return heap[0]                      # root is kth largest
```

**Optimized B -- Quick Select**: partition-based selection. O(n) average, O(n^2) worst case (mitigated with random pivot).

```python theme={null}
import random
def findKthLargest(nums, k):
    target = len(nums) - k             # kth largest = (n-k)th smallest by index

    def quickselect(lo, hi):
        pivot = nums[random.randint(lo, hi)]
        # three-way partition for robustness against duplicates
        lt, i, gt = lo, lo, hi
        while i <= gt:
            if nums[i] < pivot:
                nums[lt], nums[i] = nums[i], nums[lt]
                lt += 1; i += 1
            elif nums[i] > pivot:
                nums[gt], nums[i] = nums[i], nums[gt]
                gt -= 1
            else:
                i += 1
        if target < lt:
            return quickselect(lo, lt - 1)
        elif target > gt:
            return quickselect(gt + 1, hi)
        else:
            return nums[target]

    return quickselect(0, len(nums) - 1)
```

**Why interviewers love both**: heap demonstrates a classic data structure; Quick Select demonstrates that you understand partitioning is the real engine of quicksort and can be reused for selection.

### LC 56 -- Merge Intervals (Medium)

**Brute force**: compare every pair, merge if they overlap, repeat until no more merges happen. O(n^2) per pass, potentially many passes.

**Optimized**: sort by start time, then linear scan. O(n log n) time.

```python theme={null}
def merge(intervals):
    intervals.sort(key=lambda x: x[0])     # sort by start
    result = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= result[-1][1]:          # overlap with last merged interval
            result[-1][1] = max(result[-1][1], end)
        else:
            result.append([start, end])
    return result
```

**Why sorting by start works**: any overlapping intervals must be adjacent in start-sorted order. This turns a global pairwise-comparison problem into a local one-pass scan.

### LC 252 / 253 -- Meeting Rooms I & II (Easy / Medium)

**LC 252 (can a person attend all meetings?)**: sort by start, check if any meeting starts before the previous ends. O(n log n).

```python theme={null}
def canAttendMeetings(intervals):
    intervals.sort(key=lambda x: x[0])
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i - 1][1]:
            return False
    return True
```

**LC 253 (minimum rooms required)**: two valid approaches.

**Approach A -- min-heap of end times** (most idiomatic):

```python theme={null}
import heapq
def minMeetingRooms(intervals):
    intervals.sort(key=lambda x: x[0])
    heap = []                                # holds end times of in-use rooms
    for start, end in intervals:
        if heap and heap[0] <= start:        # earliest-ending room is free
            heapq.heappop(heap)
        heapq.heappush(heap, end)
    return len(heap)
```

**Approach B -- separate sorted arrays of starts and ends** (sweep line):

```python theme={null}
def minMeetingRooms(intervals):
    starts = sorted(i[0] for i in intervals)
    ends = sorted(i[1] for i in intervals)
    rooms = used = j = 0
    for start in starts:
        if start < ends[j]:
            used += 1                        # need a new room
            rooms = max(rooms, used)
        else:
            j += 1                           # a meeting ended -- reuse its room
    return rooms
```

**Both are O(n log n)**. The heap approach maps more naturally to "track active rooms"; the sweep-line is more elegant if you only care about the count.

### LC 75 -- Sort Colors / Dutch National Flag (Medium)

**Brute force**: count 0s, 1s, 2s, then overwrite the array. O(n) time, two passes, O(1) space. Works -- but the interviewer specifically wants ONE pass.

**Optimized -- three-way partition** in one pass, O(n) time, O(1) space:

```python theme={null}
def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    # invariant:
    #   nums[0..low-1]       == 0
    #   nums[low..mid-1]     == 1
    #   nums[mid..high]      unprocessed
    #   nums[high+1..end]    == 2
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1; mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:                                # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
            # do NOT advance mid -- the swapped-in value is unprocessed
```

**The subtle bug to avoid**: when swapping a 2, do not advance mid. The element you just pulled in from `high` has not been classified yet. Advancing mid in that case skips a potential 0 or 1.

**Why this matters beyond this problem**: three-way partitioning is the fix for quicksort's degenerate behavior on inputs with many duplicates. It is the basis of "3-way quicksort" used when keys repeat heavily.

## Curated LeetCode List

A focused grind list. Solve all of these and you have covered the sorting-pattern surface area at FAANG.

| #    | Problem                                     | Difficulty | Pattern                           | Why It Matters                                        |
| ---- | ------------------------------------------- | ---------- | --------------------------------- | ----------------------------------------------------- |
| 75   | Sort Colors                                 | Medium     | Dutch flag (3-way partition)      | One-pass partitioning -- a fundamental subroutine.    |
| 252  | Meeting Rooms                               | Easy       | Sort by start, scan               | Building block for the harder sibling.                |
| 49   | Group Anagrams                              | Medium     | Sort each string as canonical key | Sort-based hashing.                                   |
| 179  | Largest Number                              | Medium     | Custom comparator                 | Tests that you understand transitivity.               |
| 280  | Wiggle Sort                                 | Medium     | Sort + interleave                 | Demonstrates "sort first, then place" pattern.        |
| 524  | Longest Word in Dictionary through Deleting | Medium     | Sort dictionary by length desc    | Sort + scan.                                          |
| 215  | Kth Largest Element in an Array             | Medium     | Heap of size K or Quick Select    | The canonical kth-element problem.                    |
| 253  | Meeting Rooms II                            | Medium     | Sort + heap of end times          | The "intervals + heap" pattern.                       |
| 56   | Merge Intervals                             | Medium     | Sort by start, then merge         | The most-asked interval problem.                      |
| 57   | Insert Interval                             | Medium     | Linear scan with no sort needed   | Tests that you notice sorting is unnecessary.         |
| 435  | Non-overlapping Intervals                   | Medium     | Sort by end, greedy keep          | Classic activity-selection.                           |
| 452  | Minimum Number of Arrows                    | Medium     | Sort by end, count groups         | Same skeleton as LC 435.                              |
| 274  | H-Index                                     | Medium     | Sort or counting sort             | Two equally valid approaches.                         |
| 581  | Shortest Unsorted Continuous Subarray       | Medium     | Sort + compare to original        | Tests when sorting is the diagnostic, not the answer. |
| 4    | Median of Two Sorted Arrays                 | Hard       | Binary search on partition        | Sort-aware but not a sort.                            |
| 295  | Find Median from Data Stream                | Hard       | Two heaps                         | Streaming variant of the sorting problem.             |
| 1235 | Maximum Profit in Job Scheduling            | Hard       | Sort by end + DP                  | Sort enables clean DP.                                |
| 218  | The Skyline Problem                         | Hard       | Sweep line + heap                 | Combines sort, heap, and event processing.            |
| 632  | Smallest Range Covering K Lists             | Hard       | Heap of K heads                   | K-way merge variant.                                  |

**Suggested order**: 75 to 252 to 49 to 179 to 215 to 56 to 57 to 253 to 435 to 452 to 274 to 581 to 295 to 4 to 1235 to 218.

## Interview Q\&A -- Senior-Level Walkthroughs

<AccordionGroup>
  <Accordion title="Q: Sort an array of 0s, 1s, 2s in O(n) one pass (Dutch National Flag).">
    **What interviewers are really testing:** Whether you can hold three loop invariants in your head simultaneously and write code that respects all of them. The two-pass counting solution works but does not demonstrate the partitioning insight, which is the entire point of asking this question.

    **Strong Answer Framework:**

    1. Identify that the array has only three distinct values, so a constant-time decision per element suffices.
    2. Define three pointers: `low` (boundary between 0s and 1s), `mid` (current scan position), `high` (boundary between unprocessed and 2s).
    3. Walk through the three cases: see a 0 (swap to low, advance both), see a 1 (advance mid), see a 2 (swap to high, decrement high but DO NOT advance mid).
    4. State the invariants and why they are maintained.
    5. Show the code and trace one example.

    **Real LeetCode Example -- LC 75 (full code):**

    ```python theme={null}
    def sortColors(nums):
        low, mid, high = 0, 0, len(nums) - 1
        while mid <= high:
            if nums[mid] == 0:
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:                              # nums[mid] == 2
                nums[mid], nums[high] = nums[high], nums[mid]
                high -= 1
                # critically: do NOT advance mid here
    ```

    **Walkthrough for `[2, 0, 2, 1, 1, 0]`:**

    * low=0, mid=0, high=5. nums\[0]=2 -- swap with nums\[5]=0. arr becomes `[0,0,2,1,1,2]`. high=4. mid stays at 0.
    * low=0, mid=0, high=4. nums\[0]=0 -- swap with itself. low=1, mid=1.
    * low=1, mid=1, high=4. nums\[1]=0 -- swap with itself. low=2, mid=2.
    * low=2, mid=2, high=4. nums\[2]=2 -- swap with nums\[4]=1. arr becomes `[0,0,1,1,2,2]`. high=3. mid stays.
    * low=2, mid=2, high=3. nums\[2]=1 -- mid=3.
    * low=2, mid=3, high=3. nums\[3]=1 -- mid=4. Loop exits.
    * Result: `[0,0,1,1,2,2]`. Correct.

    <Note>
      **Senior follow-up 1**: "Why do you not advance mid when swapping a 2?" Answer: the element you just pulled in from `high` is unprocessed -- you do not know if it is 0, 1, or 2. If you advance mid, you skip classifying it. By contrast, when you swap a 0 into the `low` region, the value you pull out of `low` was already classified as a 1 (by the invariant: everything between `low` and `mid` is 1), so it is safe to advance both pointers.
    </Note>

    <Note>
      **Senior follow-up 2**: "Generalize this to K distinct values, not just 3." Answer: K-way partitioning generally requires K-1 passes or K pointers. Three is the sweet spot because it can be done in one pass with three pointers. For K=4, you can do two Dutch-flag passes (split into "below median" and "above median," then sort each side). For arbitrary K, you would just use a regular comparison sort -- the constant-time per-element decision only works when the value set is tiny and known.
    </Note>

    <Note>
      **Senior follow-up 3**: "How does this generalize to quicksort with three-way partitioning?" Answer: instead of using a fixed value (1), use the chosen pivot. After partitioning, all values equal to the pivot are clustered in the middle and do not need to be recursed on. This restores O(n log n) for inputs with many duplicate keys, where standard Lomuto partitioning would degrade to O(n^2).
    </Note>

    **Common Wrong Answers:**

    * "Count the 0s, 1s, 2s, then overwrite." Two passes -- works but misses the point of the question.
    * Standard quicksort or any comparison sort. O(n log n) when O(n) is achievable.
    * Advancing mid when swapping a 2. Subtle bug that produces wrong output on `[2, 0, 1]` (you skip the 0 that came from high).

    **Further Reading:**

    * LC 75 (Sort Colors) -- the source problem.
    * LC 215 (Kth Largest) with three-way Quick Select -- robust to duplicates.
    * "Quicksort with 3-way partitioning" by Robert Sedgewick (Princeton) -- the canonical reference.
  </Accordion>

  <Accordion title="Q: Merge K sorted lists / arrays. Discuss heap vs divide-and-conquer.">
    **What interviewers are really testing:** Whether you can analyze two valid approaches with the same asymptotic complexity but different real-world trade-offs. This is a staff-level differentiator.

    **Strong Answer Framework:**

    1. Brute force: collect everything, sort, rebuild. O(N log N) where N is total elements.
    2. Approach A -- min-heap of K heads: O(N log K). Each element is pushed and popped once.
    3. Approach B -- divide-and-conquer pairwise merge: O(N log K). log K rounds of O(N) work each.
    4. Compare: heap is simpler, easier to extend to streaming. D\&C has better cache locality and parallelizes naturally.

    **Real LeetCode Example -- LC 23 with heap (full code):**

    ```python theme={null}
    import heapq
    def mergeKLists(lists):
        heap = []
        for i, node in enumerate(lists):
            if node:
                # tuple: (value, tiebreaker_index, node)
                heapq.heappush(heap, (node.val, i, node))
        dummy = ListNode(0)
        tail = dummy
        while heap:
            val, i, node = heapq.heappop(heap)
            tail.next = node
            tail = node
            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))
        return dummy.next
    ```

    **Why O(N log K)?** Each of N total elements is pushed and popped from a heap of size at most K. Each operation is O(log K). Total: O(N log K).

    **Divide-and-conquer alternative** does log K rounds of merging, each round processing all N elements in pairwise merges. Same O(N log K).

    <Note>
      **Senior follow-up 1**: "Why is the index in the heap tuple necessary?" Answer: Python's heapq compares tuples lexicographically. When two values are equal, it falls through to the next element. ListNode has no `__lt__` method, so without the index it raises TypeError. The index is a unique tiebreaker that ensures every tuple is comparable. Java's PriorityQueue avoids this by accepting a Comparator directly.
    </Note>

    <Note>
      **Senior follow-up 2**: "What if K is huge but each list is tiny?" Answer: heap approach uses O(K) memory. If K is in the millions, this is a problem. Divide-and-conquer keeps only O(log K) recursion frames in memory at a time (and the in-progress merge result). For very large K, D\&C wins on space.
    </Note>

    <Note>
      **Senior follow-up 3**: "Could you parallelize the merge?" Answer: divide-and-conquer is naturally parallel -- the K/2 pairwise merges in round 1 are independent. This is exactly the structure of parallel merge sort. The heap approach is inherently sequential because each pop depends on previous pops. For very large K with available cores, parallel D\&C wins decisively.
    </Note>

    **Common Wrong Answers:**

    * "Merge them sequentially -- merge list 1 with list 2, then with list 3, etc." This is O(K \* N): early lists are re-traversed at each step.
    * Using a max-heap and reversing. Wastes time and signals confusion about heap direction.
    * Forgetting to push `node.next` after popping. Result is incomplete -- only the original heads come out.

    **Further Reading:**

    * LC 23 (Merge K Sorted Lists) -- the source problem.
    * LC 378 (Kth Smallest in Sorted Matrix) -- heap K-way merge applied to rows.
    * LC 632 (Smallest Range Covering K Lists) -- a sliding-window variant on K-way merge.
  </Accordion>

  <Accordion title="Q: Custom comparators -- sort an array of strings to form the largest concatenated number (LC 179).">
    **What interviewers are really testing:** Whether you can design a comparator that satisfies strict weak ordering (transitivity, asymmetry, totality), and whether you understand that the sort key is not always the obvious one.

    **Strong Answer Framework:**

    1. Recognize that lexicographic sort of `["3", "30", "34"]` gives `["3", "30", "34"]`, which produces "33034" -- wrong. We want "34330".
    2. The correct comparator: for any two strings a, b, prefer the order that produces the larger concatenation. So a should come before b if `a + b > b + a` as strings.
    3. Prove transitivity: if `a + b > b + a` and `b + c > c + b`, then `a + c > c + a`. This is a known property of string concatenation comparison.
    4. Use language-appropriate comparator API.

    **Real LeetCode Example -- LC 179 (full code):**

    ```python theme={null}
    from functools import cmp_to_key
    def largestNumber(nums):
        strs = list(map(str, nums))
        # comparator: a before b if a+b > b+a (we want larger first, so return -1)
        def compare(a, b):
            if a + b > b + a:
                return -1
            elif a + b < b + a:
                return 1
            else:
                return 0
        strs.sort(key=cmp_to_key(compare))
        result = ''.join(strs)
        return '0' if result[0] == '0' else result      # handle [0,0,0] edge case
    ```

    **Java version (uses Comparator):**

    ```java theme={null}
    public String largestNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) strs[i] = String.valueOf(nums[i]);
        Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));   // descending
        if (strs[0].equals("0")) return "0";
        StringBuilder sb = new StringBuilder();
        for (String s : strs) sb.append(s);
        return sb.toString();
    }
    ```

    <Note>
      **Senior follow-up 1**: "Why is `return a - b` a buggy comparator?" Answer: when `a` and `b` are near INT\_MAX or INT\_MIN, the subtraction overflows and produces wrong-signed results. For example, `Integer.MIN_VALUE - 1` overflows to `Integer.MAX_VALUE`. Always use `Integer.compare(a, b)` in Java, or explicit if/else returning -1/0/1, to avoid this. This is a real bug that has shipped in production codebases.
    </Note>

    <Note>
      **Senior follow-up 2**: "Prove transitivity for the string concatenation comparator." Answer: not entirely trivial -- it follows from the fact that the comparison defines a total order on the multiplicative group of strings. A short argument: define f(a,b) = 1 if a+b > b+a, else -1. Then f is a strict total order because string concatenation has a consistent lexicographic property. The formal proof appears in standard algorithm texts; in an interview, you would say "I would verify transitivity by induction on length" rather than attempt a full proof.
    </Note>

    <Note>
      **Senior follow-up 3**: "What if your comparator is not transitive? What happens?" Answer: in Java, `Arrays.sort` will throw `IllegalArgumentException: Comparison method violates its general contract` (added in Java 7 for safety). In C++, you get undefined behavior -- the sort may produce wrong output, run forever, or crash. In Python, the sort completes but produces an undefined ordering. Always test your comparator on small examples before trusting it.
    </Note>

    **Common Wrong Answers:**

    * Sorting numerically descending: gives "34330" only by coincidence on small inputs; fails on `[3, 30, 34, 5, 9]` which should be `9534330`.
    * Sorting strings lexicographically: gives "9534303" (close but wrong on the 30/3 ordering).
    * Returning a boolean from the comparator instead of -1/0/1: works in JavaScript by accident (false coerces to 0, true to 1) but fails in Java and C++.

    **Further Reading:**

    * LC 179 (Largest Number) -- the source problem.
    * LC 937 (Reorder Data in Log Files) -- another nontrivial comparator.
    * LC 1366 (Rank Teams by Votes) -- multi-key comparator.
  </Accordion>

  <Accordion title="Q: Find the median of an unsorted array. Compare full sort vs Quick Select.">
    **What interviewers are really testing:** Whether you can recognize that you do not need the entire array sorted -- you only need one specific element. This is the gateway question to selection algorithms.

    **Strong Answer Framework:**

    1. Brute force: sort, return middle. O(n log n) time, O(1) extra space if in-place.
    2. Optimized: Quick Select. Find the (n/2)th smallest in O(n) average time using partitioning.
    3. State the worst case: O(n^2) without randomization. With random pivot or median-of-medians, O(n) worst case.
    4. Mention real-world: C++ `std::nth_element` is exactly this algorithm.

    **Real LeetCode Example -- Quick Select for median:**

    ```python theme={null}
    import random
    def findMedian(nums):
        n = len(nums)
        target = n // 2

        def quickselect(lo, hi):
            pivot = nums[random.randint(lo, hi)]
            lt, i, gt = lo, lo, hi
            while i <= gt:
                if nums[i] < pivot:
                    nums[lt], nums[i] = nums[i], nums[lt]
                    lt += 1; i += 1
                elif nums[i] > pivot:
                    nums[gt], nums[i] = nums[i], nums[gt]
                    gt -= 1
                else:
                    i += 1
            if target < lt:
                return quickselect(lo, lt - 1)
            elif target > gt:
                return quickselect(gt + 1, hi)
            else:
                return nums[target]

        if n % 2 == 1:
            return quickselect(0, n - 1)
        else:
            # for even n, average the two middle values
            a = quickselect(0, n - 1)
            target = n // 2 - 1
            b = quickselect(0, n - 1)
            return (a + b) / 2
    ```

    **Why O(n) average?** Each recursive call processes about half the array. The recurrence T(n) = T(n/2) + O(n) sums to O(2n) = O(n) -- a geometric series.

    <Note>
      **Senior follow-up 1**: "What is the median-of-medians algorithm?" Answer: a deterministic pivot selection that guarantees the partition splits the array into chunks of at least 30%/70%, yielding O(n) worst case for selection. The constant factor is large -- often 10x slower than randomized in practice -- so it is rarely used outside theoretical contexts. Know it exists; do not use it in interviews unless asked.
    </Note>

    <Note>
      **Senior follow-up 2**: "What if the data is too large to fit in memory?" Answer: external selection. Use external merge sort to sort, then read the middle element. Or use a streaming median estimator (two heaps for exact, t-digest or approximate quantile sketches for approximate). For truly huge data, approximate is the standard answer because exact median requires O(n) space which is infeasible.
    </Note>

    <Note>
      **Senior follow-up 3**: "What changes if you need a streaming median (LC 295)?" Answer: maintain two heaps -- a max-heap of the lower half and a min-heap of the upper half. Keep them balanced (sizes differ by at most 1). The median is either the top of the larger heap (odd total) or the average of both tops (even total). Each insert is O(log n); each median query is O(1). This is the canonical streaming-median pattern.
    </Note>

    **Common Wrong Answers:**

    * Sorting the whole array. Works but O(n log n) when O(n) is achievable.
    * Quick Select without randomized pivot. Worst case O(n^2) on already-sorted input -- fails on adversarial test cases.
    * Forgetting to handle even-length arrays (need the average of two middles, not just one).

    **Further Reading:**

    * LC 215 (Kth Largest Element) -- the canonical Quick Select problem.
    * LC 295 (Find Median from Data Stream) -- the streaming variant.
    * "Introduction to Algorithms" (CLRS), chapter 9 on selection.
  </Accordion>
</AccordionGroup>

## Practice Problems

<CardGroup cols={2}>
  <Card title="Sort Colors" icon="palette" href="https://leetcode.com/problems/sort-colors/">
    Dutch National Flag algorithm
  </Card>

  <Card title="Kth Largest" icon="ranking-star" href="https://leetcode.com/problems/kth-largest-element-in-an-array/">
    Quick Select technique
  </Card>

  <Card title="Merge Intervals" icon="clock" href="https://leetcode.com/problems/merge-intervals/">
    Sort then merge
  </Card>

  <Card title="Sort List" icon="list-ol" href="https://leetcode.com/problems/sort-list/">
    Merge sort for linked list
  </Card>
</CardGroup>

## Interview Questions

### 1. Compare Quick Sort and Merge Sort. When would you choose one over the other?

**What interviewers are really testing:** Whether you understand the practical trade-offs beyond textbook complexity -- stability, cache behavior, space overhead, and worst-case guarantees. This is the sorting question that separates memorizers from engineers.

**Strong Answer:**

* Both are O(n log n) on average, but the trade-offs matter in practice. Merge Sort guarantees O(n log n) in all cases and is stable (equal elements preserve order), but requires O(n) extra space for the merge buffer. Quick Sort is O(n log n) average with O(n^2) worst case, but it sorts in-place with only O(log n) stack space and has excellent cache locality because it operates on contiguous memory.
* Choose Merge Sort when stability is required (sorting objects by multiple keys), when working with linked lists (no random access needed, and the merge step uses O(1) extra space on linked lists), or when you need a worst-case guarantee (external sorting, real-time systems).
* Choose Quick Sort for in-memory arrays where average-case speed matters. Quick Sort typically outperforms Merge Sort by 2-3x in practice due to better cache behavior -- the partition step accesses elements sequentially in memory, while Merge Sort bounces between the input and a temporary buffer.
* The worst case for Quick Sort (already sorted array with last-element pivot) is mitigated with randomized pivot selection or median-of-three. In production code, libraries like Python's Timsort and Java's `Arrays.sort()` for primitives use hybrid approaches -- Timsort is a merge-sort/insertion-sort hybrid, and Java uses dual-pivot Quick Sort for primitives.

**Red flag answer:** "Quick Sort is always better because it is faster." This ignores stability, worst-case behavior, and space. Another red flag is not knowing that Quick Sort is unstable.

**Follow-ups:**

1. Why is Quick Sort preferred for arrays but Merge Sort preferred for linked lists? What changes about the cost model?
2. Explain how randomized pivot selection prevents the O(n^2) worst case. What is the probability of hitting worst case with random pivots?

***

### 2. What does it mean for a sorting algorithm to be "stable," and why does it matter in practice?

**What interviewers are really testing:** Whether you understand stability beyond the definition and can give a real scenario where it matters. Many candidates define it but cannot explain when they would actually need it.

**Strong Answer:**

* A stable sort preserves the relative order of elements that compare as equal. If two records have the same sort key, they appear in the output in the same order they appeared in the input.
* In practice, this matters when sorting by multiple criteria. Suppose you have a list of employees sorted by name, and you then sort by department. With a stable sort, employees within each department remain alphabetically sorted. With an unstable sort, the name ordering within each department is destroyed.
* Among the classic comparison sorts: Merge Sort is stable, Quick Sort and Heap Sort are not. Counting Sort and Radix Sort are stable by design, which is why Radix Sort works -- it relies on the stability of its inner counting sort passes.
* Real-world example: database ORDER BY clauses with multiple columns rely on stable sorting. Python's `sort()` is stable (Timsort), which is why you can sort by secondary key first, then primary key, and get the correct multi-key ordering.

**Red flag answer:** "Stable means the algorithm always produces the same output." That confuses stability with determinism. Another red flag is defining stability correctly but being unable to give a single practical use case.

**Follow-ups:**

1. Can you make an unstable sort stable? What is the cost?
2. Why is Heap Sort unstable? Can you give a concrete example where it reorders equal elements?

***

### 3. Explain Counting Sort. When is it faster than comparison-based sorts, and when does it fail?

**What interviewers are really testing:** Whether you understand the O(n log n) lower bound for comparison sorts and recognize that Counting Sort breaks it by not comparing elements. They also want to see if you understand the hidden cost in the "k" parameter.

**Strong Answer:**

* Counting Sort works by counting the frequency of each value, then using cumulative counts to place each element directly into its correct position. It runs in O(n + k) time where k is the range of input values (max - min + 1). It does not compare elements at all -- it uses values as array indices.
* It beats comparison sorts when k is O(n) or smaller. Sorting 1 million integers all in the range \[0, 1000]? Counting Sort runs in O(n) while Quick Sort needs O(n log n). Sorting exam scores (0-100) for 10,000 students? Counting Sort is clearly superior.
* It fails when the range k is much larger than n. Sorting 100 integers in the range \[0, 10^9] requires a count array of a billion entries -- wildly impractical. It also only works on discrete values (integers or values that can be mapped to integers), not floating-point numbers or arbitrary objects.
* The stable version iterates through the input in reverse order when building the output, using the cumulative count to determine each element's position. This is important because Radix Sort depends on Counting Sort being stable.

**Red flag answer:** "Counting Sort is always O(n) so it is always the best." This ignores the k factor. Another red flag is not knowing it requires integer-like keys.

**Follow-ups:**

1. How does Radix Sort use Counting Sort internally? What is Radix Sort's total complexity?
2. There is a theorem that comparison-based sorting cannot be faster than O(n log n). How is Counting Sort not violating this?

***

### 4. You are given an array of intervals like `[[1,3], [2,6], [8,10], [15,18]]`. Merge all overlapping intervals. Walk through your approach.

**What interviewers are really testing:** Whether you can use sorting as a preprocessing step to simplify a problem. This is one of the most common interview patterns: "sort first, then apply a greedy scan."

**Strong Answer:**

* First, sort the intervals by their start time. This ensures that any overlapping intervals are adjacent in the sorted order, which turns the problem from a global check into a local one.
* Then do a single linear scan: maintain a `current` interval. For each next interval, if it overlaps with `current` (`next.start <= current.end`), merge them by extending current.end to `max(current.end, next.end)`. If it does not overlap, push `current` to the result and start a new `current`.
* Time is O(n log n) for the sort plus O(n) for the scan. Space is O(n) for the output (or O(log n) for the sort stack, depending on what counts).
* Edge cases: intervals that are fully contained within another (like \[1,10] and \[2,3] -- the merge just keeps \[1,10]), intervals that share a single boundary point (\[1,3] and \[3,5] merge into \[1,5]), and a single interval (return as-is).

**Red flag answer:** "I would check every pair of intervals to see if they overlap." That is O(n^2) and misses the sorting insight. An even worse red flag is sorting by end time instead of start time, which does not group overlapping intervals correctly.

**Follow-ups:**

1. What if instead of merging you need to find the minimum number of meeting rooms required for a set of time intervals? How does sorting help?
2. How would you insert a new interval into an already sorted, non-overlapping list and merge if necessary?

***

### 5. Explain the Dutch National Flag algorithm (three-way partitioning). Why is it useful beyond just sorting?

**What interviewers are really testing:** Whether you understand partitioning at a deeper level than Quick Sort's basic pivot. Three-way partition is a building block for problems like "Sort Colors" and is the key optimization for Quick Sort when duplicates are common.

**Strong Answer:**

* The Dutch National Flag algorithm partitions an array into three regions around a pivot value: elements less than the pivot, elements equal to the pivot, and elements greater than the pivot. It uses three pointers -- `low`, `mid`, and `high` -- and processes the array in a single O(n) pass.
* The invariant: everything before `low` is less than the pivot, everything between `low` and `mid` is equal, everything after `high` is greater, and between `mid` and `high` is unprocessed. We advance `mid` and swap elements to maintain this invariant.
* For "Sort Colors" (LeetCode 75), the three values are 0, 1, and 2. The pivot is 1. After one pass: all 0s are on the left, 1s in the middle, 2s on the right.
* Beyond Sort Colors, three-way partitioning is the fix for Quick Sort with many duplicates. Standard Lomuto partition puts equal elements on one side, leading to O(n^2) when all elements are the same. Three-way partition groups equals together and only recurses on the less-than and greater-than partitions, restoring O(n log n) performance.

**Red flag answer:** "Just count the occurrences and write them back." While this works for Sort Colors specifically, it does not generalize and misses the partitioning concept entirely. Interviewers want to see the in-place swap logic.

**Follow-ups:**

1. Walk me through the pointer movements for the array `[2, 0, 1, 2, 0, 1]` step by step.
2. How does Quick Sort's performance degrade with many duplicate keys, and how does three-way partitioning fix it?

***

### 6. What is Quick Select and how does it find the kth largest element in O(n) average time?

**What interviewers are really testing:** Whether you understand that you can apply the partitioning idea from Quick Sort without fully sorting the array. This tests the ability to recognize that partial work suffices.

**Strong Answer:**

* Quick Select uses Quick Sort's partition step, but instead of recursing on both halves, it only recurses on the half that contains the kth element. After partitioning, the pivot is at its final sorted position `p`. If `p == k`, we are done. If `k < p`, recurse on the left half. If `k > p`, recurse on the right half.
* Average time is O(n): the recurrence is T(n) = T(n/2) + O(n), which sums to O(2n) = O(n). This is because each recursive call cuts the problem roughly in half, and the total work across all levels forms a geometric series.
* Worst case is O(n^2) for the same reason as Quick Sort -- a bad pivot picks the smallest or largest element every time. Mitigation: use randomized pivot selection or the "median of medians" algorithm for a guaranteed O(n) worst case (though the constant factor is large, so randomized is preferred in practice).
* Real-world usage: finding the median of an unsorted array, finding percentiles, the kth smallest in a stream. C++'s `std::nth_element` uses a variant of this algorithm.

**Red flag answer:** "Just sort and return the kth element." That is O(n log n) and misses the entire point. Another red flag is not being able to explain why the average case is O(n) -- the geometric series argument.

**Follow-ups:**

1. What is the "median of medians" algorithm? How does it guarantee O(n) worst case, and why is it rarely used in practice?
2. If you needed the kth largest element from a continuous stream of data, would Quick Select still work? What would you use instead?

***

### 7. Why do most standard library implementations use hybrid sorting algorithms instead of a pure Quick Sort or Merge Sort?

**What interviewers are really testing:** Production awareness and understanding that theoretical complexity is not the whole story. This separates textbook knowledge from engineering maturity.

**Strong Answer:**

* Hybrid sorts combine the strengths of multiple algorithms to handle different input sizes and patterns. Python's Timsort (used in `list.sort()` and Java's `Arrays.sort()` for objects) is a merge-sort/insertion-sort hybrid. It detects already-sorted subsequences ("runs") in the data and merges them, achieving O(n) on nearly-sorted input while maintaining O(n log n) worst case.
* For small subarrays (typically n under 16 to 32), all O(n log n) algorithms are slower than Insertion Sort because the overhead of recursion, function calls, and cache misses dominates. So hybrid sorts switch to Insertion Sort below a threshold.
* Java uses dual-pivot Quick Sort for primitive arrays (better cache behavior, in-place) and Timsort for object arrays (stability required for objects since `equals()` behavior must be preserved).
* Introsort (used in C++ `std::sort`) starts with Quick Sort, monitors recursion depth, and switches to Heap Sort if the depth exceeds 2 \* log(n) -- this prevents the O(n^2) worst case while getting Quick Sort's cache benefits in the average case.

**Red flag answer:** "Library sorts are just Quick Sort." This is factually wrong and shows the candidate has not investigated how real systems work. Another red flag is not knowing what Timsort is despite using Python or Java.

**Follow-ups:**

1. What is the significance of "runs" in Timsort? How does it exploit partially sorted data?
2. If you were implementing a sort for a database engine that needs to sort data larger than memory, which algorithm would you choose and why?