CODEWITHSUNDEEP
algorithmmergesort
Psypher
Psypher

Reputation: 21

Best Case For Merge Sort

I've made a program that count cost of mergesort algorithm for different value of n, i've taken cost variable and i am incrementing it every time loop encounter or condition chech occure and when i get sorted array i gave that sorted array in and input to merge sort again and after that in third case i am reversing the sorted array so it would be worst case but for all three cases i am getting the same cost,so what would be the Best And Worst Case For Mergesort.

Upvotes: 2

Views: 11067

Answers (1)

chqrlie
chqrlie

Reputation: 145297

The cost of mergesort implemented classically either as a top-down recursive function or a bottom-up iterative with a small local array of pointers is the same: O(N.log(N)). The number of comparisons will vary depending on the actual contents of the array, but by at most a factor of 2.

You can improve this algorithm at a linear cost by adding an initial comparison between the last element of the left slice and the first element of the right slice in the merge phase. If the comparison yields <= then you can skip the merge phase for this pair of slices.

With this modification, a fully sorted array will sort much faster, with a linear complexity, making it the best case, and a partially sorted array will behave better as well.

Upvotes: 2

Related Questions