Изменения

'''Терпеливая сортировка '''(англ. ''patience sorting'') {{---}} алгоритм сортировки с худшей сложностью <tex>O(n</tex> <tex>\log</tex> <tex>n)</tex>. Позволяет также вычислить длину [[LISЗадача о наибольшей возрастающей подпоследовательности|наибольшей возрастающей подпоследовательности]] данного массива. Алгоритм назван по одному из названий карточной игры "Солитёр" {{---}} "Patience".

Создадим массив [[стек|стеков]] для хранения стопок. При раскладывании элементов по стопкам для поиска самой левой подходящей стопки используем [[бинарный Целочисленный двоичный поиск|бинарный поиск]]. Соответственно, поиск самой левой стопки занимает <tex>O(\log</tex> <tex>p)</tex>, где p {{---}} количество стопок (стеков). Таким образом, временная сложность раскладывания по стопкам не превышает <tex>O(n \cdot \log n)</tex>.Для получения отстортированного массива используем [[бинарная Двоичная куча|бинарную кучу]]. На каждом шаге алгоритма необходимо извлечь из кучи стек с минимальной вершиной за <tex>O(\log</tex> <tex>p)</tex>, где p - количество стеков в куче. Снять вершину выбранного стека и вернуть его в кучу за <tex>O(\log</tex> <tex>p)</tex>. Получение отсортированного массива займёт <tex>O(n \cdot \log</tex> <tex>n)</tex> времени.