| title | date | lastmod |
|---|---|---|
Merge Sort |
2022-11-08 |
2022-11-21 |
Divide and Conquer
- Divide the problem recursively into smaller (n/2) sub problems
- When only 1 element remains, this subproblem is considered trivially sorted
- 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
[!NOTE] 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
[!NOTE] 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 $$
