W ciągu sześciu ostatnich artykułów o sortowaniu opisałem najbardziej znane podejścia do sortowania oraz kilka wywodzących się od nich. Algorytmów sortowania jest jednak bardzo wiele i nie byłem w stanie omówić wszystkich tych, które planowałem. W tym artykule opisuję trzy algorytmy, które miały znaleźć się wcześniej na blogu, jednak z różnych powodów odłożyłem je na później — sortowanie odd-even, gnoma oraz drzewiaste.

Przez ostatnie cztery artykuły poświęcone sortowaniu omawialiśmy sobie różne sposoby, w jaki sposób porównywać elementy, a następnie zamieniać, by odbyło się to z jak najmniejszą liczbą porównań, co też przekładać się miało na jak najszybszy czas wykonania algorytmu. Porównywanie elementów wydaje się być czymś całkowicie naturalnym, bo przecież jak możemy ustalić kolejność bez tego? Ano, można. I w tym artykule pokażę, jak to można zrobić.

W poprzednich częściach serii opisywałem, w jaki sposób tworzyć algorytmy sortowania bazujące na tym, jak na co dzień sortujemy, oraz jak podejścia te można optymalizować. Jednak, jak mogłeś się przekonać, nie są to najszybsze rozwiązania, dlatego teraz przejdziemy do omawiania tych mniej oczywistych podejść do sortowania, które okazują się być wydajniejsze. Omówimy algorytmy, które bazują na metodzie „dziel i zwyciężaj”.