Стабільне сортування

Масив прізвищ (дані) і років народження (ключі):

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^** отримано нестабільним впорядкуванням.

За час ${\displaystyle \;O(n^{2})}$

• сортування вставкою
• сортування обміном

За час ${\displaystyle O(n\log \;n)}$

• сортування злиттям

За час ${\displaystyle \;O(n)}$ з використанням додаткової інформації про елементи

• сортування підрахунком
• сортування за розрядами
• сортування комірками

За час ${\displaystyle O(n\log ^{2}\;n)}$

• сортування злиттям модифіковане

• Алгоритм сортування
• Нотація Ландау — нотація «велике О».

• Thimas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press. ISBN 0-07-013151-1