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: Divide the array into halves. Recursively sort each half. Merge the sorted halves.

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:
- Divide the array into halves.
- Recursively sort each half.
- Merge the sorted halves.