Piyush: Your solution takes O(n) extra stack space and is
inadmissible. Kunal's idea of using an insertion/bubble sort mechanism
will work in O(n^2) with O(1) extra memory.
DK
On Jun 7, 10:36 pm, Apoorve Mohan <apoorvemo...@gmail.com> wrote:
> @piyush: at every call to merge u create 3 variables...so u consider this an
> in-place solution???
>
> On Tue, Jun 7, 2011 at 11:03 PM, Piyush Sinha <ecstasy.piy...@gmail.com>wrote:
>
>
>
>
>
>
>
>
>
> > void merge(int a[], int n, int i)
> > {
>
> > if(i == 1)
> > {
> > arr[1] = arr[n];
> > arr[2] = arr[n << 1];
> > return;
> > }
> > int a = arr[i - 1];
> > int b = arr[n + i - 1];
> > int c = arr[2*n + i - 1];
>
> > merge(arr, n, i - 1);
>
> > int x = 3 * (i - 1);
> > arr[x] = a;
> > arr[x + 1] = b;
> > arr[x + 2] = c;
> > }
>
> > Call merge(a, n/3, n/3);
>
> > I am assuming n is a multiple of 3...I don't know whether the above
> > solution satisfies ur conditions...
>
> > On 6/6/11, siva viknesh <sivavikne...@gmail.com> wrote:
> > > @piyush...i think u can use anything..but give a optimal solution
>
> > > On Jun 5, 9:22 pm, Piyush Sinha <ecstasy.piy...@gmail.com> wrote:
> > >> Can we use recursion/internal stack memory???
>
> > >> On 6/5/11, hary rathor <harry.rat...@gmail.com> wrote:
>
> > >> > it it is possible in order of O(n )
>
> > >> > --
> > >> > 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.
>
> > >> --
> > >> *Piyush Sinha*
> > >> *IIIT, Allahabad*
> > >> *+91-8792136657*
> > >> *+91-7483122727*
> > >> *https://www.facebook.com/profile.php?id=100000655377926*
>
> > > --
> > > 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.
>
> > --
> > *Piyush Sinha*
> > *IIIT, Allahabad*
> > *+91-8792136657*
> > *+91-7483122727*
> > *https://www.facebook.com/profile.php?id=100000655377926*
>
> > --
> > 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
>
> Apoorve Mohan
--
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.
