CODEWITHSUNDEEP
javatime-complexitymergesort
ArcTicker
ArcTicker

Reputation: 57

What is the running time complexity after changing the merge sort

I've been trying to figure out the answer to this problem without success maybe you could lead me a little bit: We change the merge sort so that when you already sorted the array it stops and returning the array without calling to another 2 recursion calls. for example lets run the algorithm on an array that each number in the array appears exactly n/log(n) times, (so that the array contains exactly log(n) different numbers ) what will be the running time complexity now?

Upvotes: 1

Views: 759

Answers (2)

kajacx
kajacx

Reputation: 12939

"We change the merge sort so that when you already sorted the array it stops and returning the array without calling to another 2 recursion calls."

That's how normal merge sort works. After it sorts an array (or a section of the array), it does not call any more recursion calls, it just returns the sorted array. The recursion is called in order to sort the section of the array in the first place.

Perhaps you wanted to say "Before we recursively sort the 2 halves and merge them, we check if the array is already sorted". That would be useless with arrays with different numbers, as there would be an extremely low chance (1/n!) that the array would be sorted.

With your example it is more interesting, however if the array has only log(n) different numbers I would recommend ordering the unique values and creating a hashmap from value to index, which is fast on only log(n) values and then you can sort in linear time with bucket sort for example.

Upvotes: 1

chqrlie
chqrlie

Reputation: 144780

Indeed you can try and improve mergesort efficiency for sorted arrays by checking if the sorted subarrays are already in the proper order and skip the merge phase. This can be done efficiently by comparing the last element A of the left subarray for the first element B of the right subarray. If A <= B, merging is not needed.

This trick does not increase the complexity as it adds a single test to every merge phase, but it does not remove any of the recursive calls as it requires both subarrays to be sorted already. Conversely, it does reduce the complexity to linear if the array is sorted.

Another approach is the check if the array is already sorted before splitting and recursing. This adds many more tests in the general case but does not increase the complexity either as this number of tests is bounded by N log(N) as well. It is on average more expensive for unsorted arrays (more extra comparisons), but more efficient on sorted arrays (same number of tests, but no recursion).

You can try benchmarking both approaches on a variety of test cases and array sizes to measure the impact.

Upvotes: 0

Related Questions