Even after hearing. learning, programming merge sort several times in the past, suddenly I am caught in a logical knot today again. I know that Big O of Merge Sort is n*logn but
- since there are atleast 1 comparisons at the last step and
- 2 comparisons at the last but one step and
- 4 comparisons in the last but second steps and so on..
- isn’t 1 + 2 + 4 + ….n/2 = (1 – 2^logn)/(1-2) = 2^logn
- i.e. it seems the merge sort is O(2^logn).
Here’s how I untangled it by writing down a break down of all the steps involved.
- lets say values is an int array of size n.
- During merge sort we break it two halves of size n/2 and
- continue to perform the same operation on each of the halves until we get arrays of sie 1
- at this point we merge two arrays of size 1 by comparing them and we get array of size 2
- Similarly 1 comparison is required at least n/2 times
- this is because we are breaking n into n/2 two size arrays recursively.
- From above it seems that we need to make n/2 1 comparisons and n copy statements in the worst case i.e. n/2 + n are the total number of operations required to come up with n/2 sorted 2 size arrays.
- Taking this further we need (n/4)*2 + n here there are 2 comparisons required and this continues
- given above the total number of steps seems to be = (n/2 + n) + ((n/4)*2 + n) + …
- i.e. nlogn + n/2 * logn
- i.e. 3n/2 logn
QED and my mind is restored, the logical mistake that I committed was assuming that 1 comparison was required only once and 2 comparisons were required only one etc. but in fact
- 1 comparisons was required n/2 times
- 2 comparison were required n/4 times and so on untill
- n/2 comparisons which was required only once
- i.e. n/2 + n2+ … = n/2 * logn comparisons in total