Merge Sort

Last updated Nov 8, 2022 Edit Source

Divide and Conquer

1. Divide the problem recursively into smaller (n/2) sub problems
2. When only 1 element remains, this subproblem is considered trivially sorted
3. Combine sorted subproblems together (backtracking) using a merge function.

Case 3 shows how Mergesort achieves . Equal elements are placed in the merged array in the order that they appear in:

Complexity at each recursive call is due to the application of the merge function

Worst Case

• At least 1 element is moved to the new merged list after each comparison
• The final comparison will result in 2 elements moving to the merged list
• Hence, key comparisons needed to merge n elements is at most n-1
• 

Best Case

• When both subarrays are already sorted relative to each other, each comparison will move one element from the smaller array into the merged list until it is empty
  • [1,2,…,n-1, n] or [n,n-1,…,2,1] increasing or decreasing ordered arrays
• The bigger array will be appended to the end without further comparisons
• If both arrays are equal size (n/2), there will be at best $\frac{n}{2}$ key comparisons
• 
• $$T(n)=2T(\frac{n}{2})+\frac{n}{2} = \frac{n}{2}logn $$