Нитевидная сортировка :: Strand sort

В данном методе приходится постоянно удалять и вставлять элементы, поэтому он достаточно оптимален при работе с двусвязными списками.

Алгоритм

Проходим список и по пути отбираем элементы, формирующие упорядоченный подсписок.

Производим слияние текущего упорядоченного подсписка с ранее полученным.

Достаточно скромна - в среднем O(n²). Однако весьма эффективна при работе с почти упорядоченными списками - O(n).

Название	Нитевидная сортировка (Strand sort)
Класс	Сортировки слиянием
Устойчивость	Да
Сравнения	Да
Сложность по времени	Худшая	O(n²)
	Средняя	O(n²)
	Лучшая	O(n)
Сложность по памяти	Общая	O(n)