MergeSort na ciągach bitonicznych

[19Radek88]

Hej.

Mam taki problem. Do napisania mam projekt którego polecenie brzmi:

"Zaimplementowac sortowanie przez scalanie, dzialajace w oparciu o ciagi uporzadkowane bitonicznie, bez kopiowania".

Ciagi bitoniczne to takie, ktore do pewnego momentu sa caly czas niemalejace, a dalej nierosnace (lub odwrotnie). Jak jednak wykorzystać tę wiedzę do wykonania tego zadania to już nie mam pojęcia. Jeśli macie jakiś pomysł jak to zacząć, jakieś wskazówki, a może przykładowy kod, to byłbym bardzo wdzięczny.

[Zordon]

szukamy gdzie sie konczy ciag niemalejacy (czy tam nierosnacy), i sobie dzielimy tablice jakby na dwie czesci, potem odwracamy sobie jedną z części i scalamy Koniec

złożoność czasowa O(n)