Understanding the divide-and-conquer strategy of Merge Sort and its stability.
Merge Sort is a classic sorting algorithm that exemplifies the 'divide and conquer' paradigm. Its logic is beautifully simple: 1. **Divide**: If the array has more than one element, divide it into two equal halves. 2. **Conquer**: Recursively call Merge Sort on each of the two halves. 3. **Combine**: Once the two halves are sorted, merge them into a single sorted array. The base case for the recursion is an array with zero or one element, which is already considered sorted. The key operation is the `merge` step. This step takes two sorted subarrays and combines them by repeatedly picking the smaller of the two head elements and placing it into the final array until one of the subarrays is empty, at which point the remaining elements of the other are appended. Merge Sort has a guaranteed time complexity of O(n log n) in all cases (worst, average, and best), which makes it a very reliable choice. Its main drawback is that it requires O(n) auxiliary space for the merge operation, so it is not an in-place sort. A significant advantage of Merge Sort is that it is a 'stable' sort. This means that if two elements have equal keys, their relative order in the input array will be preserved in the sorted output. This property is important in certain applications.