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]