Merge Sort: Analysis
The merge sort runs in time.
Justification:
- The number of times the merge sort divides a sequence is the number of times can be halved: .
- The number of times merge sort merges the subsequences is equal to the number of sub-sequences. Therefore, the merging part also has steps.
-
Since the merge process is linear, each merge steps goes over all elements.
-
So the total running time for the merge sort algorithm is ,
Formal Proof
A more formal proof can be constructed by writing the runtime of merge sort as a recurrence relation and showing .
If you want to look this up, search for "the master theorem for divide-and-conquer recurrences" and look up "case 2". This is, however, beyond the scope of this course.
Resources
- Wikipedia's entry on Merge sort: Analysis.
- Wikipedia's entry on Master Theorem.