Merge Sort

## How Merge Sort Works

Merge Sort is a divide-and-conquer algorithm that divides the array into halves, recursively sorts them, and then merges the sorted halves back together.

### Algorithm Steps:
1. Divide the array into two halves
2. Recursively sort each half
3. Merge the two sorted halves into one sorted array
4. Base case: Arrays of size 0 or 1 are already sorted

### Key Characteristics:
- **Stable**: Equal elements maintain their relative order
- **Predictable**: Always O(n log n) regardless of input
- **Extra space**: Requires O(n) auxiliary space for merging