Merge Sort & Quick Sort

[!NOTE] This module explores the core principles of Merge Sort & Quick Sort, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. The Hook: The O(N log N) Barrier

To break the O(N²) barrier, we need a new way of thinking: Divide and Conquer. Instead of trying to sort the whole list at once, we break it down until it’s trivial (size 1), and then combine.

• Merge Sort: The reliable workhorse. Stable. Guaranteed O(N log N).
• Quick Sort: The speed demon. Unstable. O(N²) worst case, but O(N log N) average with lower constants.

---

2. Merge Sort: Reliability

Philosophy: “Sorting is hard. Merging two sorted lists is easy.”

1. Divide: Split array in half.
2. Conquer: Recursively sort both halves.
3. Combine: Merge the two sorted halves into one.

Mathematical Anchor: Recurrence Relation

T(N) = 2T(N/2) + O(N) By Master Theorem, this is O(N log N).

Stability

Merge Sort is Stable. If we have two items (5, "A") and (5, "B"), and they appear in that order, mergesort guarantees (5, "A") comes before (5, "B"). This is crucial for multi-column sorting (e.g., sort by First Name, THEN sort by Last Name).

---

3. Quick Sort: Raw Speed

Philosophy: “Do the work during the divide step.”

1. Partition: Pick a Pivot. Move everything smaller to left, everything larger to right.
2. Conquer: Recursively sort left and right partitions.
3. Combine: Nothing! The array is already sorted in place.

The Pivot Problem

If we pick the first element as pivot, and the array is already sorted:

• Partition puts 0 elements on left, N-1 on right.
• Recursion depth becomes N instead of log N.
• Time becomes O(N²).

Solution: Pick Random Pivot or Median-of-3.

---

4. Implementation: Quick Sort (Lomuto Partition)

public void quickSort(int[] arr, int low, int high) {
  if (low < high) {
    int p = partition(arr, low, high);
    quickSort(arr, low, p - 1);
    quickSort(arr, p + 1, high);
  }
}

private int partition(int[] arr, int low, int high) {
  int pivot = arr[high]; // Choosing last element as pivot
  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;
}

func QuickSort(arr []int, low, high int) {
  if low < high {
    p := partition(arr, low, high)
    QuickSort(arr, low, p-1)
    QuickSort(arr, p+1, high)
  }
}

func partition(arr []int, low, high int) int {
  pivot := arr[high]
  i := low - 1

  for j := low; j < high; j++ {
    if arr[j] < pivot {
      i++
      arr[i], arr[j] = arr[j], arr[i]
    }
  }
  arr[i+1], arr[high] = arr[high], arr[i+1]
  return i + 1
}

---

5. Hardware Reality: Cache Locality

Why is Quick Sort often faster than Merge Sort in RAM?

1. Locality: Quick Sort works in-place. It moves pointers i and j linearly toward each other. This is a dream for CPU pre-fetchers.
2. Memory: Merge Sort requires O(N) extra space (auxiliary array). Allocating and writing to this memory takes bandwidth.

However, for Linked Lists or Disk Storage, Merge Sort wins because it accesses data sequentially without random jumps.

---