Merge Sort
Merge Sort is a divide-and-conquer algorithm that sorts an array by recursively dividing it into smaller subarrays, sorting each subarray, and then merging the sorted subarrays back together. The key idea is that two sorted arrays can be merged into one sorted array efficiently.
Let's say we want to sort the array [8, 3, 1, 7, 0, 10, 2].
1. **Divide:** The array is recursively divided into subarrays until each subarray contains only one element (which is considered sorted).
[8, 3, 1, 7, 0, 10, 2] -> [8, 3, 1, 7] and [0, 10, 2] -> [8, 3] and [1, 7] and [0, 10] and [2] -> [8], [3], [1], [7], [0], [10], [2]
2. **Conquer:** Each subarray with a single element is already sorted.
3. **Merge:** The subarrays are merged in a sorted manner.
[8] and [3] are merged to [3, 8]
[1] and [7] are merged to [1, 7]
[0] and [10] are merged to [0, 10]
[2] remains [2]
[3, 8] and [1, 7] are merged to [1, 3, 7, 8]
[0, 10] and [2] are merged to [0, 2, 10]
[1, 3, 7, 8] and [0, 2, 10] are merged to [0, 1, 2, 3, 7, 8, 10]
The final sorted array is [0, 1, 2, 3, 7, 8, 10].Merge Sort guarantees a time complexity of O(n log n) in all cases (best, average, and worst), where n is the number of elements in the array. This is because the divide step takes O(log n) time, and the merge step takes O(n) time. The algorithm also requires O(n) auxiliary space due to the temporary arrays created during the merge process. Merge Sort is a stable sorting algorithm, meaning that elements with equal values maintain their relative order in the sorted output.