Advanced Sorting (Merge/Quick)

To sort millions of records, $O(N^2)$ algorithms are completely unusable. We need advanced sorting algorithms that utilize the Divide & Conquer paradigm to achieve $O(N \log N)$ time complexity.

1. Merge Sort

Merge Sort repeatedly divides the array in half until each subarray contains only 1 element (which is technically sorted). Then, it continuously merges the sorted subarrays back together.

• Time Complexity: $O(N \log N)$ (Always)
• Space Complexity: $O(N)$ (Requires temporary arrays during the merge phase)

Implementation

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

function merge(left: number[], right: number[]): number[] {
  const result: number[] = [];
  let i = 0; let j = 0;
  
  // Compare elements and insert the smallest into result
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i]); i++;
    } else {
      result.push(right[j]); j++;
    }
  }
  
  // Push remaining elements
  return result.concat(left.slice(i)).concat(right.slice(j));
}

2. Quick Sort

Quick Sort selects a "Pivot" element and partitions the array such that all elements smaller than the pivot are moved to the left, and all elements larger are moved to the right. It then recursively applies this to the left and right subarrays.

• Time Complexity: $O(N \log N)$ (Average), $O(N^2)$ (Worst case if bad pivot is chosen)
• Space Complexity: $O(\log N)$ (In-place, but recursive call stack takes space)

[!TIP] Despite the $O(N^2)$ worst-case, Quick Sort is often heavily preferred in real-world systems because its $O(\log N)$ space complexity makes it much more cache-friendly than Merge Sort. Many language engines (like V8) use variations of Quick Sort.

Implementation

function quickSort(arr: number[], left = 0, right = arr.length - 1): number[] {
  if (left < right) {
    const pivotIndex = partition(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);  // Sort left of pivot
    quickSort(arr, pivotIndex + 1, right); // Sort right of pivot
  }
  return arr;
}

function partition(arr: number[], left: number, right: number): number {
  const pivot = arr[right]; // Choose last element as pivot
  let i = left - 1; // Tracks the boundary of elements smaller than pivot
  
  for (let j = left; j < right; j++) {
    if (arr[j] < pivot) {
      i++;
      swap(arr, i, j);
    }
  }
  
  // Swap pivot to its final correct position
  swap(arr, i + 1, right);
  return i + 1;
}

function swap(arr: number[], i: number, j: number) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

3. Heap Sort

Heap Sort utilizes the Min/Max Heap data structure. It builds a Max Heap from the array in $O(N)$ time. Then, it continually extracts the maximum element (the root) and places it at the end of the array, restoring the heap property each time in $O(\log N)$.

• Time Complexity: $O(N \log N)$ (Always)
• Space Complexity: $O(1)$ (In-place)

Unlike Quick Sort, Heap Sort guarantees $O(N \log N)$ in the worst case. Unlike Merge Sort, it requires no extra $O(N)$ array memory. However, in physical benchmarks, Quick Sort is usually faster due to better CPU caching.