@Anand, @Abhishek Thanks for the code and discussion.
However I am not clear as to how the approach suggested is running in O(n) time. We are dividing and calling bitonicmerge() on two parts recursively. So this should run in O(n log n) time complexity as shown below T(n) = n/2 + 2T(n/2) = n/2 + 2[n/4 + 2T(n/4)] = n/2 + n/2 + 4[n/8 + 2T(n/8)] = n/2 + n/2 + n/2 + ....log n terms (because we are doubling base each time so it should be log n terms] = n [ 1/2 + 1/2 + 1/2 + ...log n terms] = n [ (log n)/2] = 1/2*(n log n ) = O(n log n) Also all the following links mention this approach to be O(n log^2(n)) in best case and O(n log n) in worst case http://www.extreme.indiana.edu/sage/pcxx_ug/subsection3_6_2.html http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm http://en.wikipedia.org/wiki/Bitonic_sorter Some explanation on how this is O(n) will be of great help. Thanks in Advance. Sourav On Jul 3, 1:35 am, Abhishek Sharma <jkabhishe...@gmail.com> wrote: > @Anand: good one > > On Sat, Jul 3, 2010 at 2:02 AM, Anand <anandut2...@gmail.com> wrote: > > This is an example of bitonic sequence if we reverse the bottom half of the > > array. > > Sequence is called Bitonics if the sequence of number first > > increases(ascending order) and then decrease(descending order). > > > 1. We need to reverse the bottom half the array to make it bitonic. > > 2. Appy Bitonic Merge to get the final sorted array.: Complexity.O(n) > > > In the below code, I have implemented sorting n/w to sort any kind of array > > but for bitonic sequence we only bitonic merge function call which take > > O(n). > > Refer section Sorting network from Corman for more details > > >http://codepad.org/ZhYEBqMw > > > On Fri, Jul 2, 2010 at 11:30 AM, ANKUR BHARDWAJ <ankibha...@gmail.com>wrote: > > >> Given an array of n elements and an integer k where k<n. Elemnts > >> {a[0].....a[k] and a[k+1].....a[n] are already sorted. Give an > >> algorithm to sort in O(n) time and O(1) space. > > >> -- > >> You received this message because you are subscribed to the Google Groups > >> "Algorithm Geeks" group. > >> To post to this group, send email to algoge...@googlegroups.com. > >> To unsubscribe from this group, send email to > >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.