• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

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

 
Greenhorn
Posts: 16
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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!!
 
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You would appear to have posted in the wrong forum. Never mind, I can move you.
 
Ranch Hand
Posts: 62
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic