programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Analyzing time complexity of k-way merge operation for merge sort

Greenhorn
Posts: 16
Hi!! I am trying to analyze the complexity of merge procedure for merge sort to combine k sorted arrays with n elements into a single sorted array of kn elements My understanding so far on this:
1. Step 1: Firstly creating an output array of size n*k then create a min heap of size k and insert first element in all the arrays into a heap.
2. Step 2:Then get minimum element from heap(which always at root) and store it in an output array and replace heap root with next element from the array from which the element is extracted.If doesn't have any more elements in array then replace with infinite.
2. Step 3: Repeat the 2nd step n*k times.
This approach of merging sorted arrays takes O(nk*Logk) time using Min Heap.
Please suggest with some more ideas and detailed explanation. Thanks in advance!!

Campbell Ritchie
Marshal
Posts: 56227
171
You would appear to have posted in the wrong forum. Never mind, I can move you.

Lucian Whiteman
Ranch Hand
Posts: 62
kamal lamgade wrote:Hi!! I am trying to analyze the complexity of merge procedure for merge sort to combine k sorted arrays with n elements into a single sorted array of kn elements My understanding so far on this:
1. Step 1: Firstly creating an output array of size n*k then create a min heap of size k and insert first element in all the arrays into a heap.
2. Step 2:Then get minimum element from heap(which always at root) and store it in an output array and replace heap root with next element from the array from which the element is extracted.If doesn't have any more elements in array then replace with infinite.
2. Step 3: Repeat the 2nd step n*k times.
This approach of merging sorted arrays takes O(nk*Logk) time using Min Heap.
Please suggest with some more ideas and detailed explanation. Thanks in advance!!

This is the standard, I have seen it many times before.

One optimization would be to write 1) and 2) as fast as possible. Since you need to get both the min element out of the heap and at the same time to know what array out of those k it came from, try to write that code as fast as possible. It will not change overall complexity though.

Second optimization would be in step 3, not to repeat the heap thing (step 2) for n*k times. For example if all elements from all arrays but one have already been taken out of the heap, you do not need to add the remaining ones from the last array into the heap then extract them. You need to just add those. Also write this code by trying to avoid as much as possible to check for each element extracted out of the heap that only a single array remains thus you need not to add another one to the heap.

 It is sorta covered in the JavaRanch Style Guide.