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 <[email protected]>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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[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.
