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.

3 Years
Discussion Span
Last Post by 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.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.