Sortowanie Komiczne jest przykładem prostego algorytmu sortowania dowolnych elementów, ale o bardzo wysokiej złożoności obliczeniowej. Z tego powodu należy ten algorytm brać bardziej jako ciekawostkę niż jako faktyczny algorytm do zaimplementowania.
Sortowanie odbywa się w sposób rekurenycjny. Początkowo zakres sortowania jest od pierwszego elementu do ostatniego. Podczas sortowania dla wybranego zakresu porównywane są skrajne elementy zakresu i jeśli potrzebują zamiany to są zamieniane. Następnie sortowana jest pierwsze 2/3 zakresu, następnie ostatnie 2/3 zakresu i na koniec pierwsze 2/3 zakresu. Oczywiście sortowanie jest zaniedbywane, gdy już nie jest możliwy podział zakresy na kolejne podzakresy.
Załóżmy, że do posortowania jest tablica L:={6, 1, 7, 5}. Nawiasami kwadratowymi [] został zaznaczony aktualnie przeglądany zakres. Wykonane zostaną następne operacje:
| Tablica | Lewy | Prawy | Komentarz |
|---|---|---|---|
| {[6,1,7,5]} | 6 | 5 | Zamiana |
| {[5,1,7],6} | 5 | 7 | |
| {[5,1],7,6} | 5 | 1 | Zamiana |
| {1,[5,7],6} | 5 | 7 | |
| {[1,5],7,6} | 1 | 5 | |
| {1,[5,7,6]} | 5 | 6 | |
| {1,[5,7],6} | 5 | 7 | |
| {1,5,[7,6]} | 7 | 6 | Zamiana |
| {1,[5,6],7} | 5 | 6 | |
| {[1,5,6],7} | 1 | 6 | |
| {[1,5],6,7} | 1 | 5 | |
| {1,[5,6],7} | 5 | 6 | |
| {[1,5],6,7} | 1 | 5 |
Jak można zauważyć już dla zaledwie 4 elementów liczba potrzebnych porównań wynosi 13 podczas, gdy nawet algorytm sortowania bąbelkowego wykonałby ich tylko 6. Algorytmowi zajmuje bardzo dużo czasu dodatkowa potrzeba na porównywanie elementów z zakresów, które się na siebie nakładają.
Przyjmuje się, że złożoność algorytmu wynosi O(n~2.71), a złożoność pamięciowa wynosi O(n). Wynika ona z faktu, że dla każdego wywołania funkcji istnieje potrzeba przechowywania danych na temat poprzedniego zakresu.
Przygotowanie sortowania algorytmem Komicznym nie jest trudne, ponieważ sortowanie odbywa się w sposób rekurencyjny i instrukcję sortowania wystarczy jedynie zapisać w wybranym języku programowania. Oto przykładowa implementacja, która sortuje dane zapisane w tablicy tab. Zmienne L i P oznaczają kolejny lewy i prawy indeks wybranego zakresu:
W każdym wywołaniu jeśli (2.) istnieje potrzeba zamiany skrajnych elementów to należy ją (3. - 7.) wykonać, a następnie (8.) jeśli istnieje możliwość podziału za 3 zakresy to (9. - 12.) należy posortować odpowiednie grupy zgodnie z podanym wcześniej algorytmem.
Dla wygody wywoływania funkcji sortuj() warto dopisać jej przeciążenie, które nie będzie wymagać zakresu:
W celu przetestowania napisanej funkcji sortujące można skorzystać z poniższego fragmentu kodu, który wczyta rozmiar tablicy, jej elementy, a następnie wypisze posortowaną tablice.