EXTRA: Merge Sort

Merge Sort is a classic divide-and-conquer algorithm.

It works by dividing the array into smaller parts, sorting each part, and then merging them back together.

General idea:

1. Divide the array into halves.
2. Recursively sort each half.
3. Merge the sorted halves.

👉 Merge Sort has a time complexity of O(n log n).

Merge Sort Function

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

  const middle = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, middle));
  const right = mergeSort(arr.slice(middle));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];

  while (left.length && right.length) {
    if (left[0] < right[0]) result.push(left.shift());
    else result.push(right.shift());
  }

  return result.concat(left, right);
}

🧩 Example Recap

If you call:

mergeSort([5, 2, 4, 7])

Split into [5, 2] and [4, 7]

[5, 2] → split into [5] and [2]

Merge [5] and [2] → [2, 5]

[4, 7] → split into [4] and [7]

Merge [4] and [7] → [4, 7]

Now merge [2, 5] and [4, 7]

Final result: `[2, 4, 5, 7]