sort all the arrays first O(nlogn) then use merge sort
On Sat, Jul 16, 2011 at 3:43 PM, Ankur Khurana <[email protected]>wrote: > Use divide and conquer. take 2 array at a time and .so you are merging two > array at a time. > > num_of_list=m; > length of list=n; > > while(num_of_list > 1) > { > while( (num of list where length = length_of_list) >2) > { > merge two lists of length (length_of_list); > > } > if(num_of_list %2==0) > num_of_list/=2; > else > num_of_list/=2+1; > length of list=n; > > } > (it is just a general idea , you have to take care of the left over list > every time , the check for that i havent posted) > > so time complexity is > > > 2*n* (m/2) + 2* 2n* (m/4) .............. log(m) times. > > so complexity is n*m*log(m) > > > > > > On Sat, Jul 16, 2011 at 2:43 PM, aseem garg <[email protected]> wrote: > >> Q2. Given m arrays of n size each, give an algorithm to combine these >> arrays into a single array with sorted elements. Also tell the time >> complexity of your solution. >> Aseem >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
