Patience sorting is a sorting algorithm, based on a solitaire card game, that has the property of being able to efficiently compute the length of the longest increasing subsequence in a given array. In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ... This article is about the solitaire family of card games. ... A card game is any game using playing cards, either traditional or game-specific. ... In computer programming, an array, also known as a vector or list, is one of the simplest data structures. ...

The card game

The game begins with a shuffled deck of cards, labeled . The term shuffle can also refer to the act of dragging ones feet on the ground while walking, running or dancing. ...

The cards are dealt one by one into sequence of piles on the table, according to the following rules.

1. Initially, there are no piles. The first card dealt forms a new pile consisting of the single card.
2. Each new lower value card may be placed either on an existing pile that has a higher value card on the top, thus increasing the number of cards in that pile, or to the right of all of the existing piles, thus forming a new pile.
3. When there are no more cards remaining to deal, the game ends.

The object of the game is to finish with as few piles as possible. D. Aldous and P. Diaconis ([1], p.414) suggest defining 9 or fewer piles as a winning outcome for n = 52, which has approximately 5% chance to happen.

Algorithm for sorting

Given an n-element array with an ordering relation as an input for the sorting, consider it as a collection of cards, with the (unknown in the beginning) statistical ordering of each element serving as its index. Note that the game never uses the actual value of the card, except for comparison between two cards, and the relative ordering of any two array elements is known. In mathematics, a total order or linear order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ... In mathematics, the concept of binary relation is exemplified by such ideas as is greater than and is equal to in arithmetic, or is congruent to in geometry, or is an element of or is a subset of in set theory. ...

Now simulate the patience sorting game, played with the greedy strategy, i.e., placing each new card on the leftmost pile that is legally possible to use. At each stage of the game, under this strategy, the labels on the top cards of the piles are increasing from left to right. To recover the sorted sequence, collect the minimum card from the top row each time. Greedy algorithms are algorithms which follow the problem solving meta-heuristic of making the locally optimum choice at each stage with the hope of finding the global optimum. ...

For a description of an efficient implementation with worst-case running time for putting the cards into piles (which makes the worst case for a complete sort O(nlogn)) and O(n) space spent for supporting structures, relying on a van Emde Boas tree, please see the work by S. Bespamyatnikh and M. Segal ([4], pp.7–8). In computer science, best and worst cases in a given algorithm express what the resource usage is at least and at most, respectively. ... The title given to this article is incorrect due to technical limitations. ...

Algorithm for finding the longest increasing subsequence

First, execute the sorting algorithm as described above. The resulting number of piles will equal the length of the longest increasing subsequence. Whenever a card is placed on top of a pile, put a back-pointer to the top card in the previous pile (that, by assumption, has a lower value than the new card has). In the end, follow the back-pointers from the top card in the last pile to recover a decreasing subsequence of the longest length; its reverse is an answer to the longest increasing subsequence algorithm. In computer science, a pointer is a programming language datatype whose value is used to refer to (points to) another value stored elsewhere in the computer memory. ...

S. Bespamyatnikh and M. Segal ([4], pp.3–5) give a description of an efficient implementation of the algorithm, incurring no additional asymptotic cost over the sorting one (as the back-pointers storage, creation and traversal require linear time and space). They further show how to report all the longest increasing subsequences from the same resulting data structures. In mathematics and applications, particularly the analysis of algorithms, asymptotic analysis is a method of classifying limiting behaviour, by concentrating on some trend. ... A binary tree, a simple type of branching linked data structure. ...

History

According to D. Aldous and P. Diaconis ([1], p.417) patience sorting was first recognized as an algorithm to compute the longest increasing subsequence length by Hammersley ([2], p.362), and by A.S.C. Ross and independently Bob Floyd as a sorting algorithm. Initial analysis was done by Mallows [3]. Robert W Floyd (June 8, 1936 - September 25, 2001) was an eminent computer scientist. ...

References

[1] David Aldous and Persi Diaconis. Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bull. (new series) of the Amer. Math. Society, Volume 36, number 4, pages 413–432 Persi W. Diaconis (born January 31, 1945) is an American mathematician and former professional magician. ...

[2] J.M. Hammersley. A few seedlings of research. In Proc. Sixth Berkeley Symp. Math. Statist. and Probability, Volume 1, pages 345–394. University of California Press, 1972. MR 53:9457 John Michael Hammersley (21 March 1920-2 March 2004) was a British mathematician known for his foundational work in percolation theory. ...

[3] C.L. Mallows. Patience sorting. Bull. Inst. Math. Appl., 9:216–224, 1973.

[4] Sergei Bespamyatnikh and Michael Segal. Enumerating Longest Increasing Subsequences and Patience Sorting. Pacific Inst. for the Math. Sci. Preprints, PIMS-99-3.