Merge sort divides the array in half, recursively sorts each half, then merges the sorted halves.
The idea: Divide: Split the array into two halves.
Conquer: Recursively sort each half.
Combine: Merge the two sorted halves into one sorted array.
Example for :
Split into and . Recursively sort each to get and . Merge to get .
The merge step does the real work. Each element is compared and placed in order.