Merge Sort Complexity – How the Dividing Step in Merge Sort Has Constant Time Complexity

algorithm-analysisalgorithmscomplexitysorting

I am highly confuse while calculating time complexity of Merge Sort Algorithm.
Specifically on the Dividing Step.
In the dividing step we have to calculate the mid point of "n" i.e. "q = n/2".

How it will take constant time.
If we assume that divide is an elementary operation and take very less time, then also we should include the time taken by divide.

Suppose If we have to divide very large amount of time then it must be consider while calculating the time complexity.
According to me Number of divides depends on "n" i.e. Calculating mid point depends on the array size "n".

For Example,

if n = 2

Number of divides required = 1

if n = 4

Number of divides required = 3

if n = 8

Number of divides required = 7

if n = 16

Number of divides required = 15 and so on….

According to me,

If Recursively Define:-

Number of Divide needed for "n" (input array length = n) <= 1 + Number of divides needed for (n-1).
{when n = 0 Number of divides = 0
when n = 1 Number of divides = 0}

Or……….

Number of Divide needed for "n" (input array length = n) <= (Summation of 2^i from 0 to n-1) – (2^n)

So, it depends on "n". So how we can take it as a constant time????

Best Answer

I'm glad you took the time to try to understand this apparent discrepancy. You're correct that we do need to account for the divisions, and that for this algorithm, we have ~n divisions. In general, if we are dividing reasonably small numbers (those that fit in a long), we count that individual division operation as effectively O(1), so we have O(n) divisions.

What you're missing is that it doesn't really matter, because we already have an O(n) operation in the mix: the merge. In this particular case, that's why adding the divisions in doesn't change the overall complexity from O(n log n). Accounting for the divisions would change it to O(2n log n) and constants get factored out.

Related Solutions

Merge sort versus quick sort performance

If you look at your code for swapping you:

// If current element is lower than pivot
// then swap it with the element at store_index
// and move the store_index to the right.

But, ~50% of the time that string you just swapped needs to be moved back, which is why faster merge sorts work from both ends at the same time.

Next if you check to see if the first and last elements are the same before doing each of the recursive call you avoid wasting time calling a function only to quickly exit it. This happens 10000000 in your final test which does add noticeable amounts of time.

Use,

if (pivot_index -1 > start) quick_sort(lines, start, pivot_index - 1);

if (pivot_index + 1 < end) quick_sort(lines, pivot_index + 1, end);

You still want an outer function to do an initial if (start < end) but that only needs to happen once so that function can just call an unsafe version of your code without that outer comparison.

Also, picking a random pivot tends to avoid N^2 worst case results, but it's probably not a big deal with your random data set.

Finally, the hidden problem is QuickSort is comparing strings in ever smaller buckets that are ever closer together,

(Edit: So, AAAAA, AAAAB, AAAAC, AAAAD then AAAAA, AAAAB. So, strcmp needs to step though a lot of A's before looking the useful parts of the strings.)

but with Merge sort you look at the smallest buckets first while they are vary random. Mergsorts final passes do compare a lot of strings close to each other, but it's less of an issue then. One way to make Quick sorts faster for strings is to compare the first digits of the outer strings and if there the same ignore them when doing the inner comparisons, but you have to be careful that all strings have enough digits that your not skipping past the null terminator.

Why is time complexity of k-way merge sort O(nk^2)

the recursion depth is log n/log k,

merging costs n*log k, using a min heap for log k per element

thus we come at T(n) = n* log k + K* T(n/k) which (unless I'm mistaken) becomes n log n (actually n (c_1/k+log(n))= n/k + n*log(n) but the n/k becomes insignificant in big O)

Best Answer

Related Solutions

Merge sort versus quick sort performance

Why is time complexity of k-way merge sort O(nk^2)

Related Topic