Sorting — The Complete Guide

function sortAndScan(arr: number[][]): Result {
  // 1. Sort by the relevant key
  arr.sort((a, b) => a[0] - b[0]);

  // 2. Linear scan — compare each element with the previous
  const result = [arr[0]];
  for (let i = 1; i < arr.length; i++) {
    const prev = result[result.length - 1];
    const curr = arr[i];

    if (overlaps(prev, curr)) {
      merge(prev, curr);  // extend/update the previous
    } else {
      result.push(curr);  // start a new group
    }
  }

  return result;
}
// When to use: merge intervals, remove covered intervals,
// minimum number of arrows, meeting rooms

function customSort(arr: Item[]): Item[] {
  return arr.sort((a, b) => {
    // Primary sort key
    if (a.primary !== b.primary) {
      return a.primary - b.primary;
    }
    // Secondary sort key (tiebreaker)
    return a.secondary - b.secondary;
  });
}

// String concatenation comparator (Largest Number):
strs.sort((a, b) => (b + a).localeCompare(a + b));

// Multi-key sort (sort by frequency, then by value):
arr.sort((a, b) => freq[a] - freq[b] || a - b);

// When to use: largest number, custom sort string,
// sort by frequency, relative sort array

function sortThenSearch(arr: number[], target: number): Result {
  // 1. Sort the array
  arr.sort((a, b) => a - b);

  // 2. Apply Two Pointers on sorted data
  let left = 0, right = arr.length - 1;
  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === target) return [arr[left], arr[right]];
    if (sum < target) left++;
    else right--;
  }

  return notFound;
}
// When to use: 3Sum, 4Sum, two sum (when indices don't matter),
// closest pair, minimum absolute difference

function threeWayPartition(arr: number[], pivot: number): void {
  let low = 0, mid = 0, high = arr.length - 1;

  while (mid <= high) {
    if (arr[mid] < pivot) {
      [arr[low], arr[mid]] = [arr[mid], arr[low]];
      low++;
      mid++;
    } else if (arr[mid] === pivot) {
      mid++;
    } else {
      [arr[mid], arr[high]] = [arr[high], arr[mid]];
      high--;
      // Don't advance mid — swapped element is unchecked
    }
  }
}
// When to use: Sort Colors (0/1/2), partition around pivot,
// move negatives to left / positives to right

function largestNumber(nums: number[]): string {
  const strs = nums.map(String);

  // Custom comparator: which concatenation order is bigger?
  strs.sort((a, b) => {
    const ab = a + b;
    const ba = b + a;
    return ba.localeCompare(ab); // descending — bigger first
  });

  // Edge case: all zeros → "000..." should be "0"
  if (strs[0] === "0") return "0";

  return strs.join("");
}
// Time: O(n log n) — sorting with string comparisons
// Space: O(n) — storing string representations
// Key: the comparator (a, b) => (b+a).localeCompare(a+b) is transitive,
// which guarantees the sort produces the globally optimal order.

function minMeetingRooms(intervals: number[][]): number {
  const starts = intervals.map(i => i[0]).sort((a, b) => a - b);
  const ends = intervals.map(i => i[1]).sort((a, b) => a - b);

  let rooms = 0, maxRooms = 0;
  let s = 0, e = 0;

  while (s < starts.length) {
    if (starts[s] < ends[e]) {
      rooms++;    // a meeting starts before the earliest one ends
      s++;
    } else {
      rooms--;    // a meeting ends — free up a room
      e++;
    }
    maxRooms = Math.max(maxRooms, rooms);
  }

  return maxRooms;
}
// Time: O(n log n) for sorting
// Space: O(n) for the separate arrays
// Key insight: we don't need to track WHICH meeting ends —
// just that SOME meeting ends before the next one starts.

function topKFrequent(nums: number[], k: number): number[] {
  // 1. Count frequencies
  const freq = new Map<number, number>();
  for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1);

  // 2. Bucket sort: index = frequency, value = list of numbers
  const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);
  for (const [num, count] of freq) {
    buckets[count].push(num);
  }

  // 3. Collect from highest frequency bucket
  const result: number[] = [];
  for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
    result.push(...buckets[i]);
  }

  return result.slice(0, k);
}
// Time: O(n) — no comparison sort needed
// Space: O(n) for frequency map and buckets
// Why bucket sort? Frequency is bounded by n, so bucket index fits in [0, n].

Input: [[1,3], [2,6], [8,10], [15,18]]

Step 1: Sort by start time
  → [[1,3], [2,6], [8,10], [15,18]]  (already sorted)

Step 2: Initialize merged = [[1,3]]

Step 3: Process [2,6]
  prev = [1,3], curr = [2,6]
  curr.start (2) ≤ prev.end (3) → OVERLAP
  Merge: prev.end = max(3, 6) = 6
  merged = [[1,6]]

Step 4: Process [8,10]
  prev = [1,6], curr = [8,10]
  curr.start (8) > prev.end (6) → NO OVERLAP
  Push new interval
  merged = [[1,6], [8,10]]

Step 5: Process [15,18]
  prev = [8,10], curr = [15,18]
  curr.start (15) > prev.end (10) → NO OVERLAP
  Push new interval
  merged = [[1,6], [8,10], [15,18]]

Answer: [[1,6], [8,10], [15,18]]

Key: After sorting by start, we only compare with the LAST merged interval.
Overlapping intervals are always adjacent in sorted order.

Input: [2, 0, 2, 1, 1, 0]
       low=0, mid=0, high=5

Step 1: arr[mid]=2 → swap with high, high--
  [0, 0, 2, 1, 1, 2]  low=0, mid=0, high=4

Step 2: arr[mid]=0 → swap with low, low++, mid++
  [0, 0, 2, 1, 1, 2]  low=1, mid=1, high=4

Step 3: arr[mid]=0 → swap with low, low++, mid++
  [0, 0, 2, 1, 1, 2]  low=2, mid=2, high=4

Step 4: arr[mid]=2 → swap with high, high--
  [0, 0, 1, 1, 2, 2]  low=2, mid=2, high=3

Step 5: arr[mid]=1 → mid++
  [0, 0, 1, 1, 2, 2]  low=2, mid=3, high=3

Step 6: arr[mid]=1 → mid++
  [0, 0, 1, 1, 2, 2]  low=2, mid=4, high=3

mid > high → STOP

Answer: [0, 0, 1, 1, 2, 2]

Invariant maintained at every step:
  [0..low-1] = all 0s
  [low..mid-1] = all 1s
  [high+1..end] = all 2s
  [mid..high] = unprocessed

Input: [3, 30, 34, 5, 9]
Convert to strings: ["3", "30", "34", "5", "9"]

Custom comparator: (a, b) => (b+a).localeCompare(a+b)

Comparisons during sort:
  "3" vs "30":  "303" vs "330" → "330" > "303" → 3 before 30  ✓
  "3" vs "34":  "343" vs "334" → "343" > "334" → 34 before 3  ✓
  "5" vs "3":   "35" vs "53"   → "53" > "35"   → 5 before 3   ✓
  "9" vs "5":   "59" vs "95"   → "95" > "59"   → 9 before 5   ✓
  "9" vs "34":  "349" vs "934" → "934" > "349"  → 9 before 34  ✓

Sorted order: ["9", "5", "34", "3", "30"]

Join: "9534330"

Answer: "9534330"

Key: The comparator (b+a) vs (a+b) is transitive — if a > b and b > c,
then a > c. This guarantees the sort produces the globally optimal order.

Does the problem involve intervals or ranges?
├── YES → Sort by start (merging) or end (greedy selection)
└── NO  → Does the problem need a custom ordering?
          ├── YES → Custom comparator sort
          └── NO  → Would sorted order enable Two Pointers or Binary Search?
                    ├── YES → Sort first, then apply the pattern
                    └── NO  → Is the value range small and bounded?
                              ├── YES → Counting sort or Dutch National Flag (O(n))
                              └── NO  → Do you need top-K by frequency?
                                        ├── YES → Bucket sort or Heap
                                        └── NO  → Sorting probably isn't the right pattern
                                                  → Consider Hashing, Sliding Window, or DP