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

kamal lamgade

Greenhorn

Posts: 16

posted 1 year ago

Hi!! I am trying to analyze the complexity of

1.

2.

2.

This approach of merging sorted arrays takes

**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

Sheriff

Posts: 51468

87

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 ofmerge procedure for merge sortto 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 takesO(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.