Sorting: Merge Sort & Quick Sort Mechanics

Dynamic Arrays & Amortized Resizing

Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.

1. Divide-and-Conquer Sorting

Comparison-based sorting has a mathematical theoretical lower bound of $O(N log N)$. Merge Sort and Quick Sort are the two foundational divide-and-conquer sorting algorithms.

2. Merge Sort (Stable & Guaranteed O(N log N))

Merge Sort divides the array into two halves, recursively sorts each half, and merges the two sorted halves:

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const leftSorted = mergeSort(arr.slice(0, mid));
  const rightSorted = mergeSort(arr.slice(mid));

  return merge(leftSorted, rightSorted);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return result.concat(left.slice(i)).concat(right.slice(j));
}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// Output: [ 3, 9, 10, 27, 38, 43, 82 ]

3. Quick Sort (In-Place Partitioning)

Quick Sort picks a pivot element and partitions the array so all elements smaller than the pivot go to the left and larger elements go to the right:

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[arr.length - 1];
  const left = [];
  const right = [];

  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivot) left.push(arr[i]);
    else right.push(arr[i]);
  }

  return [...quickSort(left), pivot, ...quickSort(right)];
}

4. Comparison Matrix

5. Common Mistakes

• Worst-Case Pivot in Quick Sort: Choosing the first or last element on an already-sorted array triggers $O(N^2)$ quadratic degradation! Use randomized pivot selection in production.

6. Next Steps

Understand sorting guarantees for performance critical systems. Next, let's enter Phase 3 and explore Trees and Traversals!