Lekcja: "Algorytmy sortujące - sortowanie przez scalanie, sortowanie przez zliczanie"
Podsumowanie
Zarówno algorytmsortowania przez scalanie jak i algorytmsortowania przez zliczanie zaliczamy do algorytmów stabilnych czyli elementy w zbiorach sortowanych, o tych samych wartościach występują w tablicy wynikowej w takiej samej kolejności jak w tablicy wejściowej.
Klasa złożoności obliczeniowej dla algorytmu sortowania przez scalanie wynosi O(n log n), natomiast algorytmu sortowania przez zliczanie O(n + k).
Obydwa algorytmy wymagają dodatkowej pamięci – dla pierwszego O(n), natomiast w drugim przypadku O(n + k).
Oba algorytmy zalicza się do grupy algorytmów szybkich, z tym że sortowanie przez zliczanie nie wykonuje żadnych porównań elementów sortowanych, czyli może osiągać lepszą klasę złożoności obliczeniowej.