Merge Sort

Merge Sort uses a divide and conquer algorithm that is typically implemented with recursion.

• Recursively split the array into two smaller arrays.
• Base case: arrays of length one (since they are already sorted).
• Progressively merge pairs of arrays back together maintaining sorted order.