Oznacza to, że dla każdych dwóch elementów i o tym samym kluczu, jeśli wystąpiło przed , to po sortowaniu stabilnym nadal będzie przed

Kiedy elementy o tym samym kluczu są nierozróżnialne, stabilność nie jest istotna.

Przykład: (para liczb całkowitych sortowana względem pierwszej wartości)

(4, 1) (3, 7) (3, 1) (5, 6)

W tym przypadku są możliwe dwa różne wyniki sortowania:

(3, 7) (3, 1) (4, 1) (5, 6) – kolejność zachowana (3, 1) (3, 7) (4, 1) (5, 6) – kolejność zmieniona

Stabilne algorytmy sortowania gwarantują, że kolejność zostanie zachowana. Niestabilne algorytmy sortowania mogą zmienić kolejność.

Algorytmy sortujące dzieli się na proste („naiwne”) i zaawansowane („logarytmiczne”). Powstanie lepszych niż proste algorytmów sortowania, spowodowane było konsekwencjami poniższego faktu:

W losowym rozmieszczeniu elementów każdy element jest przesunięty względem swojej pozycji w posortowanym ciągu średnio o pozycji.

Jeżeli algorytm sortowania zamienia tylko elementy sąsiadujące ze sobą, musi dokonać średnio zamian dla każdego z elementów.