proc merge-sort(A, p, r) if p < r then q = floor((p + r)/2) merge-sort(A, p, q) merge-sort(A, q+1, r) merge(A, (p,q), (q+1,r))
Assuming we have equal partitions with length , the best is (consecutive partitions) is and the worst (interleaved partitions) is .
Given different sized partitions the worst case comparisons is . When is significantly less than you can use binary search to improve performance.
Merge sort comparisons
We will only analyze the worst case. The recurrence is:
The closed-form is .