CODEWITHSUNDEEP
algorithmsortingmergemergesortarray-merge
Long Smith
Long Smith

Reputation: 1401

Complexity of merge operation in merge sort

I'm reading Cormen's Introduction into algorithms.
I can't understand why merging n/k arrays with k elements in each of them has the complexity of O(n*log(n/k)).
What I'm missing here is that we have n/k arrays. Therefore, we have to perform the merge n/(k-1) times each with O(n) upper-bound.
However we have a logarithm, so I suppose that I'm missing something in my understanding of Merge complexity.

Any help is welcome.

Upvotes: 1

Views: 381

Answers (1)

amit
amit

Reputation: 178411

Assume you only can merge two arrays with merge(a,b), then you can build a "tree" of merges:

a    b      c     d
  ab           cd
       abcd

Now, it is true that using this operation you are doing indeed n/k - 1 merges - but note that most of them are done with few elements, significantly less than n elements per array.

If you calculate it carefully, you'll get:

2*(n/k)/2 * k + 2*(n/k)/4 * 2k + .... + 1*n

If you do the algebra, you'll note that this is indeed n*log(n/k).

As a side not, another way to do k-way merge is to hold a heap of size n/k, and let it hold the smallest number from each array that was not exhausted yet, and while iterating - get the smallest element in the heap to the result array.

Upvotes: 2

Related Questions