Merge Sort: Analysis

The merge sort runs in O(nlgn)O(n \lg n) time.

Justification:

  • The number of times the merge sort divides a sequence is the number of times nn can be halved: O(lgn)O(\lg n).
  • The number of times merge sort merges the subsequences is equal to the number of sub-sequences. Therefore, the merging part also has O(lgn)O(\lg n) steps.
  • Since the merge process is linear, each merge steps goes over all nn elements.

  • So the total running time for the merge sort algorithm is O(nlgn)O(n \lg n),

Formal Proof

A more formal proof can be constructed by writing the runtime of merge sort as a recurrence relation T(n)=2T(n/2)+θ(n)T(n) = 2T(n/2) + \theta(n) and showing T(n)θ(nlgn)T(n) \in \theta(n \lg n).

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