Терпеливая сортировка

Терпеливая сортировка (англ. patience sorting) - алгоритм сортировки с худшей сложностью [math]O(n[/math] [math]log[/math] [math]n)[/math]. Позволяет также вычислить длину наибольшей возрастающей подпоследовательности данного массива.

Алгоритм

тест

Реализация

тест

Пример

тест

Ссылки

• Терпеливая сортировка в английской Википедии
• Наглядное описание алгоритма на английском языке

Литература

• Sergei Bespamyatnikh and Michael Segal Pacific Inst. for the Math. Sci. Preprints, PIMS-99-3., pp.7–8