Sorting Algorithms Explained

Sorting is a building block for many other algorithms. Understanding the trade-offs between sorting algorithms : time, space, stability : is essential for interviews.

Time Complexity Comparison

Merge Sort

Divide the array in half, recursively sort each half, then merge. Stable, guaranteed O(n log n), but uses O(n) extra space.

Merge sort divides the array in half recursively, then merges sorted halves.

graph TD
    A["38, 27, 43, 3, 9, 82, 10"]
    A --> B["38, 27, 43, 3"]
    A --> C["9, 82, 10"]
    B --> D["38, 27"]
    B --> E["43, 3"]
    C --> F["9, 82"]
    C --> G["10"]
    D --> H["27, 38"]
    E --> I["3, 43"]
    F --> J["9, 82"]
    G --> K["10"]
    H --> L["3, 27, 38, 43"]
    I --> L
    J --> M["9, 10, 82"]
    K --> M
    L --> N["3, 9, 10, 27, 38, 43, 82"]
    M --> N

    style A fill:#D97A2B,stroke:#B86418,color:#fff
    style N fill:#D4EDDA,stroke:#28A745

function mergeSort(nums: number[]): number[] {
  if (nums.length <= 1) return nums;
  const mid = Math.floor(nums.length / 2);
  const left = mergeSort(nums.slice(0, mid));
  const right = mergeSort(nums.slice(mid));
  return merge(left, right);
}

function merge(a: number[], b: number[]): number[] {
  const result: number[] = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) result.push(a[i++]);
    else result.push(b[j++]);
  }
  return result.concat(a.slice(i), b.slice(j));
}

Quick Sort

Pick a pivot, partition the array into elements less than and greater than the pivot, then recurse. In-place (O(log n) stack space), but worst case O(n²) with bad pivots.

function quickSort(nums: number[], lo = 0, hi = nums.length - 1): void {
  if (lo >= hi) return;
  const pivotIdx = partition(nums, lo, hi);
  quickSort(nums, lo, pivotIdx - 1);
  quickSort(nums, pivotIdx + 1, hi);
}

function partition(nums: number[], lo: number, hi: number): number {
  const pivot = nums[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (nums[j] < pivot) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      i++;
    }
  }
  [nums[i], nums[hi]] = [nums[hi], nums[i]];
  return i;
}

When to Use Which

• Merge Sort: When stability matters (preserving relative order of equal elements). When guaranteed O(n log n) is required.
• Quick Sort: Default choice for in-memory sorting. Fastest in practice due to cache locality.
• Heap Sort: When O(1) space is required and stability is not needed.
• Counting/Radix Sort: When the range of values is small and known. O(n) time for integers.
• Built-in sort: In interviews, use nums.sort((a, b) => a - b) unless the problem asks you to implement sorting.

Common Mistakes

• Not handling duplicate elements : quick sort partition must handle elements equal to the pivot correctly.
• Confusing stability : a stable sort preserves the relative order of equal elements. Important when sorting by multiple keys.
• Using merge sort when space is constrained : merge sort requires O(n) extra space.
• Not considering the input : if the input is nearly sorted, insertion sort (O(n) best case) beats quick sort.
• Implementing sorting from scratch when not asked : use built-in sort unless explicitly asked to implement.