Member Avatar for nitin1

my algo :

1.Construct a max(min) heap from first element of all array,
2. extract a max(min) value from the heap and write to output
3. get one more element from array which the value extracted step 2 was in.
4. repeat until heap is not empty

can anyone tell me complexity of this ? according to me it is mnlogm where m is no of arrays and n is no of elements in each array. thanks.

secodnly, can we do better than this ? i have m sorted arrays and n elements in each array. i have another array of m*n elements space. so how can i merge it in most efficient way ? thanks. one of algo is given above , can we think of better ? thanks.

  • 2 Contributors
  • 1 Reply
  • 293 Views
  • 6 Hours Discussion Span
  • Latest Post Latest Post by rubberman
Member Avatar for rubberman

Myself, I prefer to use an insertion sort that uses a modified binary search (bsearch) algorithm to determine where in the output array to place a candidate key/object. It has the advantages of qsort and bsearch and the only downside (performance wise) is how you grow the target array. If you know the number of elements it will contain in advance, then that is a null-sum game. If you don't (it grows dynamically), then I have found that a binary increase in size (2x increase when needed) works pretty efficiently. The C realloc() function does that rather well... :-) The main overhead of this is to move stuff down when inserting a new element, but that is not too onerous with modern processors and the C memmove() function.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.