Merge Sort: Optimization?
You can optimize bubble sort to stop early when the input is sorted. The optimized version of bubble sort runs in $O(n)$ for the case when the input sequence is already sorted.
The merge sort algorithm can also be optimized to run in $O(n)$ when the input sequence is already sorted.
Exercise Can you come up with the optimization strategy and justify it runs in $O(n)$ when the input sequence is already sorted.
Solution
Since the (in-place) merge operation assumes the two sub-arrays (to be merged) are already sorted, we can check if the last element of the first subarray is less than or equal to the first element of the second sub-array. In that case we can escape merging:
if (a[mid - 1] > a[mid]) { // escape comparision
merge(a, left, mid, right)
}
The runtime will be $O(n)$ because the "escape comparison" is done for every pair of subarrays level by level as you merge $n$ subarrays to $n/2$ to $n/4$ to $\dots$ to $1$ array. So the total number of comparisons would be $n/2 + n/4 + n/8 + \dots + 1$ which is $O(n)$