O(n) is possible using in-shuffle but doing it in-place was the problem in case of in-shuffle we need to know which of the elements have been shuffle so we need O(n) bits of extra space;
O(nlgn) is possible using a quick sort like divide and conquer algorithm.........i read it somewhere and will post it if i am able to find it :) On Wed, Nov 2, 2011 at 7:11 PM, shady <sinv...@gmail.com> wrote: > a1 a2 a3 a4 b1 b2 b3 b4 > > given these two arrays convert them to a1 b1 a2 b2 a3 b3 a4 b4 > i can do this in O(1) space and O(n^2)time.... is there any O(n) solution > for this problem ? I searched in archives, but there people mention about > in-shuffle, but how to implement it in O(n) is not clear. > > -- > 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. > -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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.