Merge Sort

Merge sort divides the array in half, recursively sorts each half, then merges the sorted halves.

The idea: $1.$ Divide: Split the array into two halves.

$2.$ Conquer: Recursively sort each half.

$3.$ Combine: Merge the two sorted halves into one sorted array.

Example for $[38, 27, 43, 3, 9, 82, 10]$:

Split into $[38, 27, 43, 3]$ and $[9, 82, 10]$. Recursively sort each to get $[3, 27, 38, 43]$ and $[9, 10, 82]$. Merge to get $[3, 9, 10, 27, 38, 43, 82]$.

The merge step does the real work. Each element is compared and placed in order.