CODEWITHSUNDEEP
algorithmsortingtime-complexitymergesort
Shubhang Gupta
Shubhang Gupta

Reputation: 138

Running time of merge sort, all elements are identical

Given n numbers that all are identical, then what would be the running time of merge sort?

Will it be in linear time O(n) or, best case O(nlogn)

Upvotes: 1

Views: 1310

Answers (2)

rcgldr
rcgldr

Reputation: 28826

For a pure merge sort, the number of moves is always the same O(n log(n)). If all elements are the same or in order or reverse order, the number of compares is about half the number of compares for the worst case.

A natural merge sort that creates runs based on existing ordering of data would take O(n) time for all identical values or in order or reverse order. A variation of this is a hybrid insertion sort + merge sort called Timsort.

https://en.wikipedia.org/wiki/Timsort

Upvotes: 3

OmG
OmG

Reputation: 18838

You need to recheck the recursive formula that you have for the merge sort:

T(n) = 2T(n/2) + \Theta(n)

Now, when all values are identical, let see what will be changed in the formulation. \Theta(n) is for merging two subarrays. As the merging of two subarrays with identical members sweeps those arrays, independent of the identical members, it will be the same in your case.

Therefore, the recursion formula will be unchanged for the specified case; hence the time complexity will be Theta(n log n). That can be considered as one of the shortcomings of the mergesort.

Upvotes: 2

Related Questions