Analyzing time complexity of kway merge operation for merge sort
kamal lamgade
Greenhorn
Posts: 16
posted 1 year ago
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!!
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: 53147
124
Lucian Whiteman
Ranch Hand
Posts: 62
posted 1 year ago
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.
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.
Happiness is not a goal ... it's a byproduct of a life well lived  Eleanor Roosevelt. Tiny ad:
the new thread boost feature: great for the advertiser and smooth for the coderanch user
https://coderanch.com/t/674455/ThreadBoostfeature
