Editing Patience sorting

{{short description|Sorting algorithm}}
{{Infobox Algorithm
|class=[[Sorting algorithm]]
|image=
|data=[[Array data structure|Array]]
|time={{math|''O''(''n'' log ''n'')}}
|best-time={{math|''O''(''n'')}}; occurs when the input is [[adaptive sort|pre-sorted]]<ref name="Chandramouli">{{Cite conference |last1=Chandramouli |first1=Badrish |last2=Goldstein |first2=Jonathan |title=Patience is a Virtue: Revisiting Merge and Sort on Modern Processors |conference=SIGMOD/PODS |year=2014 |url=https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/patsort-sigmod14.pdf}}</ref>
|space=
|optimal=?
}}
In [[computer science]], '''patience sorting''' is a [[sorting algorithm]] inspired by, and named after, the card game [[Patience (game)|patience]]. A variant of the algorithm efficiently computes the length of a [[longest increasing subsequence]] in a given [[Array data structure|array]].

==Overview==
The algorithm's name derives from a simplified variant of the patience card game. The game begins with a shuffled deck of cards. The cards are dealt one by one into a sequence of piles on the table, according to the following rules.<ref name="Burstein">{{cite journal |journal=Séminaire Lotharingien de Combinatoire |volume=54A |year=2006 |title=Combinatorics of patience sorting piles |first1=Alexander |last1=Burstein |first2=Isaiah |last2=Lankham |url=http://www.emis.de/journals/SLC/wpapers/s54Aburlank.pdf|bibcode=2005math......6358B |arxiv=math/0506358 }}</ref>

# Initially, there are no piles. The first card dealt forms a new pile consisting of the single card.
# Each subsequent card is placed on the leftmost existing pile whose top card has a value greater than or equal to the new card's value, or to the right of all of the existing piles, thus forming a new pile.
# When there are no more cards remaining to deal, the game ends.

This card game is turned into a two-phase sorting algorithm, as follows. Given an array of {{mvar|n}} elements from some [[Total order|totally ordered]] domain, consider this array as a collection of cards and simulate the patience sorting game. When the game is over, recover the sorted sequence by repeatedly picking off the minimum visible card; in other words, perform a [[K-way merge|{{mvar|k}}-way merge]] of the {{mvar|p}} piles, each of which is internally sorted.

== Pseudocode ==
Below is an iterative implementation of Patience Sort, this implementation runs in <math>O(n^2)</math>. 
 '''function''' PatienceSorting('''array''' arr) '''is'''
     n ← '''length'''(arr)
     piles ← empty '''list''' of '''lists'''
 
     '''for''' i = 0 '''to''' n - 1 '''do'''
         '''if''' length(piles) == 0 '''then'''
             tmp ← new '''list'''
             tmp.append(arr[i])
             piles.append(tmp)
         '''else'''
             placed ← false
             '''for''' j ← 0 '''to''' length(piles) - 1 '''do'''
                 '''if''' arr[i] < last element of piles[j] '''then'''
                     piles[j].append(arr[i])
                     placed ← true
                     break
             '''if''' placed == false '''then'''
                 tmp ← new list
                 tmp.append(arr[i])
                 piles.append(tmp)
 
     '''return''' MergePiles(piles)
 
 '''function''' MergePiles(list of lists piles) '''is'''
     result ← empty '''list'''
 
     '''while''' true '''do'''
         minValue ← ∞
         index ← -1
 
         '''for''' i ← 0 '''to''' length(piles) - 1 '''do'''
             '''if''' length(piles[i]) > 0 and piles[i][length(piles[i]) - 1] < minValue '''then'''
                 minValue ← piles[i][length(piles[i]) - 1]
                 index ← i
         '''if''' minIndex = -1 '''then'''
             break
 
         result.append(minValue)
         piles[midIndex].remove(piles[midIndex][length(piles[midIndex]) - 1)
         '''if''' length(piles[minIndex]) == 0 '''then'''
             piles.remove(piles[minIndex])
 
     '''return''' result

== Analysis ==
The first phase of patience sort, the card game simulation, can be implemented to take {{math|''O''(''n'' log ''n'')}} comparisons in the worst case for an {{mvar|n}}-element input array: there will be at most {{mvar|n}} piles, and by construction, the top cards of the piles form an increasing sequence from left to right, so the desired pile can be found by [[binary search]].{{r|Chandramouli}} The second phase, the merging of piles, can be done in <math>O(n\log n)</math> time as well using a [[priority queue]].{{r|Chandramouli}}

When the input data contain natural "runs", i.e., non-decreasing subarrays, then performance can be strictly better. In fact, when the input array is already sorted, all values form a single pile and both phases run in {{math|''O''(''n'')}} time. The [[average-case]] complexity is still {{math|''O''(''n'' log ''n'')}}: any uniformly random sequence of values will produce an [[Expected value|expected number]] of <math>O(\sqrt{n})</math> piles,{{r|Bespamyatnikh}} which take <math>O(n\log\sqrt{n}) = O(n\log n)</math> time to produce and merge.{{r|Chandramouli}}

An evaluation of the practical performance of patience sort is given by Chandramouli and Goldstein, who show that a naive version is about ten to twenty times slower than a state-of-the-art [[quicksort]] on their benchmark problem. They attribute this to the relatively small amount of research put into patience sort, and develop several optimizations that bring its performance to within a factor of two of that of quicksort.{{r|Chandramouli}}

If values of cards are in the range {{math|1, . . . , ''n''}}, there is an efficient implementation with <math>O(n\log n)</math> [[worst-case]] running time for putting the cards into piles, relying on a [[Van Emde Boas tree]].<ref name=Bespamyatnikh>{{cite journal |first1=Sergei |last1=Bespamyatnikh |first2=Michael |last2=Segal |title=Enumerating Longest Increasing Subsequences and Patience Sorting |journal=[[Information Processing Letters]] |volume=76 |issue=1–2 |year=2000 |pages=7–11 |doi=10.1016/s0020-0190(00)00124-1|citeseerx=10.1.1.40.5912 }}</ref>

==Relations to other problems==
Patience sorting is closely related to a card game called Floyd's game. This game is very similar to the game sketched earlier:{{r|Burstein}}

# The first card dealt forms a new pile consisting of the single card.
# Each subsequent card is placed on ''some'' existing pile whose top card has a value no less than the new card's value, or to the right of all of the existing piles, thus forming a new pile.
# 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. The difference with the patience sorting algorithm is that there is no requirement to place a new card on the ''leftmost'' pile where it is allowed. Patience sorting constitutes a [[greedy algorithm|greedy strategy]] for playing this game.

Aldous and Diaconis suggest defining 9 or fewer piles as a winning outcome for {{math|''n'' {{=}} 52}}, which happens with approximately 5% probability.<ref name="Aldous">{{cite journal |first1=David |last1=Aldous |author-link1=David Aldous |first2=Persi |last2=Diaconis |author-link2=Persi Diaconis |url=http://www-stat.stanford.edu/~cgates/PERSI/year.html#99 |title=Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem |journal= Bulletin of the American Mathematical Society |series=New Series |volume=36 |issue=4 |pages=413–432 |doi=10.1090/s0273-0979-99-00796-x|year=1999 |doi-access=free }}</ref>

===Algorithm for finding a longest increasing subsequence===
First, execute the sorting algorithm as described above. The number of piles is the length of a longest 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.

S.&nbsp;Bespamyatnikh and M.&nbsp;Segal<ref name=Bespamyatnikh/> 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 structure]]s.

==History==
Patience sorting was named by C. L. Mallows, who attributed its invention to A.S.C. Ross in the early 1960s.{{r|Chandramouli}}
According to Aldous and Diaconis,<ref name=Aldous/> patience sorting was first recognized as an algorithm to compute the longest increasing subsequence length by Hammersley.<ref>{{cite conference |first=John |last=Hammersley |author-link=John Hammersley |title=A few seedlings of research |conference=Proc. Sixth Berkeley Symp. Math. Statist. and Probability |volume=1 |pages=345–394 |publisher=University of California Press |year=1972}}</ref> A.S.C. Ross and independently [[Robert W. Floyd]] recognized it as a sorting algorithm. Initial analysis was done by Mallows.<ref>{{cite journal |first=C. L. |last=Mallows |title=Patience sorting |journal=Bull. Inst. Math. Appl. |volume=9 |pages=216–224 |year=1973}}</ref> Floyd's game was developed by Floyd in correspondence with [[Donald Knuth]].{{r|Burstein}}

==Use==
The patience sorting algorithm can be applied to [[process control]]. Within a series of measurements, the existence of a long increasing subsequence can be used as a trend marker. A 2002 article in SQL Server magazine includes a SQL implementation, in this context, of the patience sorting algorithm for the length of the longest increasing subsequence.<ref>{{cite journal|url=http://sqlmag.com/t-sql/statistical-process-control|last=Kass|first=Steve|title=Statistical Process Control|journal=SQL Server Pro|date=April 30, 2002|access-date=23 April 2014}}</ref>

==References==
{{Reflist|30em}}

{{wikibooks|Algorithm implementation|Sorting/Patience sort|Patience sorting}}

{{sorting}}

[[Category:Comparison sorts]]
[[Category:Patience games]]