For the first one, reverse the second half of the array, and then use a bitonic merge. See, e.g., the procedure bitonic_merge in the article en.wikipedia.org/wiki/Bitonic_sorter.
For the second part, sort the second half and then go to part one, or use a bitonic sort on the second half and then a bitonic merge on the whole array. Certainly, the second part is O(n log n), and I think even the first part is of that complexity, so just ignoring the given sorted order and sorting the entire array will be of the same order. Dave On Nov 13, 9:50 am, MAC <[email protected]> wrote: > you have an array of size n where first n/2 is sorted and the sencond half > is sorted . You need to sort the entire array inplace > > Its second modification version is where first part is sorted and other is > NOT sorted . You need to make entire sorted . > -- > thanks > --mac -- 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.
