merge sort efficiency, why is it O(nlogn) ?

Thread Starter

Werapon Pat

Joined Jan 14, 2018
35

I have watched this video and I wonder about BigO of this algorithm. At first, he told that its BigO is O(nlogn), but later on (about 2:10)
he said "if we're somehow able to sort these arrays, then we can merge these two lists in original list in sorted order" which means
it requires another algorithm to sort those two arrays first, for instance bubble sort,insertion etc. So I think its efficiency shouldn't be O(nlogn)
but it depends on which algorithm that we used for sorting those two first, and then we can merge those two together, but I'm not sure about it
so correct me if I'm wrong. Thanks a lot.
 

WBahn

Joined Mar 31, 2012
26,398

I have watched this video and I wonder about BigO of this algorithm. At first, he told that its BigO is O(nlogn), but later on (about 2:10)
he said "if we're somehow able to sort these arrays, then we can merge these two lists in original list in sorted order" which means
it requires another algorithm to sort those two arrays first, for instance bubble sort,insertion etc. So I think its efficiency shouldn't be O(nlogn)
but it depends on which algorithm that we used for sorting those two first, and then we can merge those two together, but I'm not sure about it
so correct me if I'm wrong. Thanks a lot.
It requires AN algorithm to sort each half. But what if the algorithm that is used is merge sort?

At each step, the length of the array that needs to be sorted is cut in half until, eventually, the length of the array that needs to be sorted is one; how long does it take to sort an array of length one?
 
Top