Merge Sort is a divide-and-conquer algorithm that splits an array into halves, recursively sorts each half, and then merges the sorted halves back together.
- Divide: Split the array into two halves.
- Conquer: Recursively sort each half.
- Merge: Combine the sorted halves into a single sorted array.
Consider an array [38, 27, 43, 3, 9, 82, 10]. Using merge sort:
- Split into
[38, 27, 43, 3]and[9, 82, 10]. - Continue splitting until single-element arrays are obtained.
- Merge back step by step until the array is fully sorted:
[3, 9, 10, 27, 38, 43, 82].
| Complexity | Best Case | Average Case | Worst Case |
|---|---|---|---|
| Time | O(n log n) | O(n log n) | O(n log n) |
| Space | O(n) | O(n) | O(n) |