sorotowanie zbioru zbiorow

Nie wiem czy to Ci się na coś przyda ale najbardziej wydajny algorytm do sortowania jaki znam wygląda tak:
1. porządkujesz zbiór w pary i w parach sortujesz.
2. bierzesz 2 pary i porównujesz 2 najlżejsze elemeny.Lżejszy będzie 1 elementem czwórki.Element cięższy porównujesz z 2 elementem drugiej pary.itd.Jak się elementy w jednej parze skończą to przepisujesz jak leci.
3Powstałą 4 traktujesz tak samo... czyli porównujesz z następną 4. Itd. 8 16,32....
Kosztowność to n*ln2(n) czyli zbór 128 to 896.Bąbelkowe to n*n/2 czyli 8192....
Posortować podzbiory oddzielnie,a i b potraktować tą metodą i powstałe z  tego a' i b' posortować z c'.Ewentualnie stworzyć nowe zbiory A i B większe i rozlokować w nim zbiór c.Albo wszystko do jednego worka. Różnice w kosztowności będą niewielkie.Szybciej się chyba nie da.

Tu nie bylo mozliwosci porownywania elementow...

Jest tablica n-elementowa obiektow typu FOO, oraz funcja sortujaca, przyjmujaca tablice m-elementowa.

Rozwiazanie znalazlem, ale moze sie komus przya:
1. podzielic na n/m zbiorow, posortowac i zbudowac liste
2. z kazdego podzbioru wybierac 1szy i ostatni, kopiowac do pomocniczego i dodac polaczenie (czyli ostatni w liscie jest zarowno dzieckiem przedostatniego i pirwszego, 1szy jest dzieckiem ostatniego w poprzednim podzbiorze. Posortowac i przy sciaganiu z pomocniczego wyciac powiazanie z parentem, i przypsiac do 1szego elementu majacego wiecej niz jeden lisc.
3. znaalezc wezly majace wiecej niz 1 dziecko, skopiowac dzieci do pomocniczego (az do zapelnienia pomocniczej m-elementowej tablicy pomocniczej), posortowac i uzyc poprzedniego algorytmu do przebudowy drzewa.
4. jesli wszystkie elementy maja 1no dziecko to mamy posrtowana liste

Ilosc wyolania funkcji sortujacej 1-3 *(n/m) - w zaleznosci od m, gdzie np. przy m=10 wychodzi w optymistycznej wersji ~ 1.2*n/m, w pesymistycznej ~2.4*n/m

Temat zamykam