Why does merge sort require o(n) steps to merge the two sorted halves?

Assuming this is the last merging step in the algorithm: 1 3 5 7 | 13 19 20 40

Doesn't this require only n/2 steps to compare two elements at a time?


First: O(n) is the same as O(n/2), as constant factors do not matter (O(n) means there's a factor so that runtime is always less than or equal that factor times n). But also, you're wrong with n/2 comparisons.

You start with two indices, pointing to the first elements in their half.

Then, for any of the n elements, as long as there are elements left in both half-arrays, you compare those two elements, take the smaller, and increment that index. So you need up to n-1 comparisons in n steps (n-1 if the two biggest elements are not in the same array, otherwise less). This makes the merge step O(n).

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .