File PatienceSort.h

↰ Parent directory (ADS/sort)

The patience sort, beyond the book: the items are dealt, as in the card game, onto piles whose tops increase from left to right, each item on the leftmost pile whose top is not smaller than it (found by a binary search on the tops) or on a new pile; each pile is then decreasing from its bottom, and a k-way merge of the piles by a heap of their tops [see File DaryHeap.h] gives the sorted sequence, in :math:` O( n log n ) ` time.

Definition (ADS/sort/PatienceSort.h)

Detailed Description

The number of piles is the length of a longest strictly increasing subsequence, as Aldous and Diaconis tell (and lisFast() of File Subsequences.h computes), so the sort takes O( n log k ) on an input with a longest increasing subsequence of length k, e.g., O( n ) on a decreasing one.

The contracts [see File Contract.h]: the vector ends with the same items sorted, an audit. The function is defined in PatienceSort.tpp.

    1. Mallows, Patience sorting, SIAM Review 5(4), 375-376, 1963

  2. Aldous, P. Diaconis, Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem, Bulletin of the American Mathematical Society 36(4), 413-432, 1999, doi:10.1090/S0273-0979-99-00796-X

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions