Стабільним (або стійким) називається такий алгоритм сортування, що не змінює порядок елементів з однаковим ключем.
Найпоширеніша модель представлення даних для сортування — масив структур, в якому кожен елемент має поля (ключ по якому відбувається впорядкування) і їх значення (інша інформація).
Приклад
Масив прізвищ (дані) і років народження (ключі):
A = {(1988, «Знов'як»), (1984, «Олефіренко»), (1972, «Кордубан»), (1984, «Ткачук»)}
Якщо впорядкувати масив A за ключем, то можна отримати два різні результати:
A* = {(1972, «Кордубан»), (1984, «Олефіренко»), (1984, «Ткачук»), (1988, «Знов'як»)}
A** = {(1972, «Кордубан»), (1984, «Ткачук»), (1984, «Олефіренко»), (1988, «Знов'як»)}
Масиви A* і A** відрізняються порядком розташування елементів (1984, «Олефіренко») і (1984, «Ткачук») (хоча обидва масиви є впорядкованими за ключем). В A* порядок елементів з однаковими ключами такий же як і в початковому масиві A, натомість в масиві A** цей порядок змінено. Масив A* отримано стабільним впорядкуванням, тоді як масив A** отримано нестабільним впорядкуванням.
Алгоритми стабільного впорядкування
За час сортування вставкою сортування обміном
За час сортування злиттям
За час з використанням додаткової інформації про елементи сортування підрахунком сортування за розрядами сортування комірками
За час сортування злиттям модифіковане
Див. також
Алгоритм сортування Нотація Ландау — нотація «велике О».
Джерела Thimas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press. ISBN 0-07-013151-1