you sort array before merging. and then use merge sort
On Sat, Jul 16, 2011 at 6:53 PM, noobcoder <ase.as...@gmail.com> wrote:
> how does ur algo produce sorted elements in final array?
>
> On Jul 16, 3:55 pm, Ankur Khurana <ankur.kkhur...@gmail.com> wrote:
> > oops , didnt see the unsorted thing. complexity is mnlog(n) + mn log(m)
> >
> >
> >
> >
> >
> >
> >
> > On Sat, Jul 16, 2011 at 4:23 PM, sagar pareek <sagarpar...@gmail.com>
> wrote:
> > > sort all the arrays first O(nlogn)
> >
> > > then use merge sort
> >
> > > On Sat, Jul 16, 2011 at 3:43 PM, Ankur Khurana <
> ankur.kkhur...@gmail.com>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 <ase.as...@gmail.com>
> 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 algogeeks@googlegroups.com.
> > >>> To unsubscribe from this group, send email to
> > >>> algogeeks+unsubscr...@googlegroups.com.
> > >>> 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 algogeeks@googlegroups.com.
> > >> To unsubscribe from this group, send email to
> > >> algogeeks+unsubscr...@googlegroups.com.
> > >> 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 algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
Ankur Khurana
Computer Science , 4th year
Netaji Subhas Institute Of Technology
Delhi.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
