A więc średnia liczba porównań wynosi Jedynym sposobem zmniejszenia asymptotycznej złożoności algorytmów sortujących jest wprowadzenie możliwości zamieniania elementów niesąsiadujących ze sobą.
Przykładowe algorytmy sortowania W podanej złożoności oznacza liczbę elementów do posortowania, liczbę różnych elementów.
Stabilne Elementy o równej wartości będą występowały, po posortowaniu, w takiej samej kolejności, jaką miały w zbiorze nieposortowanym. sortowanie bąbelkowe (ang. bubblesort) – sortowanie przez wstawianie (ang. insertion sort) – sortowanie przez scalanie (ang. merge sort) – wymaga dodatkowej pamięci sortowanie przez zliczanie (ang. counting sort lub count sort) – wymaga dodatkowej pamięci sortowanie kubełkowe (ang. bucket sort) – wymaga dodatkowej pamięci sortowanie pozycyjne (ang. radix sort) – gdzie to wielkość domeny cyfr, a szerokość kluczy w cyfrach. Wymaga dodatkowej pamięci sortowanie biblioteczne (ang. library sort) – pesymistyczny