Editing Patience sorting (section)

== 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>