Talk:Patience sorting

Complexity

The upper bound on the algorithm can't possibly be true! How can it be a comparison sort, and have less than O(n log n)? It's not possible! gkhan 12:34, May 28, 2005 (UTC)

I agree with the O(n log n) limit. The algorithm as described seems to have complexity O(n * m), where m is the length of the longest ordered subsequence. I'm not sure what the expected value of m is, but its worst-case is clearly n (if the array is already sorted), making the algorithm O(n^2). I'm not sure how the van Emde Boas tree fits in.

I asked a question about this on comp.programming where I got a satisfactory explanation gkhan 19:47, May 29, 2005 (UTC)

Good call. By that argument, the worst case on gathering is O(n log n). One would think that the complexity to deal would be the same, but in fact you can simply keep track of the largest element seen so far, making sorted input O(n). Bovlb 02:42, 2005 May 30 (UTC)

The van Emde Boas based implementation makes asumptions about the keys range so it is not a comparison sort. Lets talk of arbitrary values and true comparison sorts. Using binary search to build the piles gives a O(n log n) algorithm. For gathering, the wikibooks implementation is not really efficient since it consist of an inteleaving of all the piles (the number of piles can be $O(n)$) and this can cost $O(n^{2})$comparisons (take $k,k-1,\ldots ,2,1,k+1,k+2,\ldots ,2k$ as initial list). A better implementation can use and preserve the fact that the top of piles are ordered. We can surely do that by insertion of the first pile in the ordered list of piles with respect to the top values ordering, however this will also cost $O(n^{2})$. Of course, to gather one can forget the structure and apply a $O(n\log n)$ sort at this point, but this can't be called a patience sort. PierreBoudes 15:07, 16 March 2007 (UTC)

I think thats exactly the point. Why generating piles and then use a Priority queue like in the Java implementation? You could just use a Priority queue in the first place and don't use the piles. It's like I invent a new sort algorithm named reverseSort: reverse the Input and then use a priority queue. And it just needs $O(n\log n)$ time, wow! Popelmaus (talk) 16:03, 25 April 2012 (UTC)

Removed from article

(To play with a regular 52-card deck, some ordering needs to be imposed, arranging the cards within a suit and imposing some order on the suits).'

Tautology. If you play with a regular 52-ccard deck, the ordering is already done for you. Project2501a 13:16, 28 May 2005 (UTC)

I feel that some context introduction is needed; when one is describing a card game, it only makes sense to explain how to play with the regular cards. Even the article [1] doesn't snub the idea of explaining it to the regular card players:

To play with real cards, one needs to linearly order the 52 cards, e.g., by putting suits in the bridge-bidding order $\clubsuit \diamondsuit \heartsuit \spadesuit$. This mindless form of solitaire is then quite playable, perhaps while watching television.

[1], p.3

BACbKA 17:25, 4 April 2006 (UTC)

Implementation code in C++

Since there seems to be no free software implementation of the patience sorting available, I finally got to posting one myself, in C++ . Currently no veb-trees are implemented, as well as no back-pointer-based sorting recovery, but it's what I myself use for a quick check of what the longest increasing subsequence length in a set is. Comes with some other C++ utilities you might like. --BACbKA 13:34, 12 May 2006 (UTC)

Thanks to User:Egkauston, who pasted a java implementation, I decided to proceed in a more fundamental way and created a patience sorting page on the wikibooks. The java code has been moved over there, and I have pasted excerpts from the above C++ code as well. See the wikibooks link in the article. --BACbKA 23:52, 1 February 2007 (UTC)

Hi, I fixed the C++ code because it used a static function in an empty class. I understand why it's necessary in Java but it is not in C++ : you can use "global" function. Other than that, I was thinking that this function could be adapted in a STL Algorithm stype by using iterators only instead of a vector but it depends on if the algorithm requires random access to elements. That said, it's only an example so it might not be necessary to do that (and maybe make it less obvious to non-C++ programmers ) Anyway I didn't touch the inside of the code. 213.39.33.80 (talk) 12:31, 24 November 2010 (UTC)

bazaar

I wonder if the fact that bazaar uses patience sort is notable enough in general (if it were, why isn't it on the bazaar article)? If it's notable in the context of the "Patience sorting" article, maybe we should create a new section detailing usage examples in known programs? if yes, what to call it? The reason I am asking is that, currently, I find the bazaar link in the "See also" section a bit sticking out of the general flow of the article, and have no trivial way in mind to smoothen it back. --BACbKA 07:46, 8 February 2007 (UTC)

I followed the citation and found no information regarding Bazaar using the Patience sorting algorithm. --Edsc86 12:20, 1 November 2009 (UTC)

It was there, but as an open wiki, revctrl.org is not a reliable source. QVVERTYVS (hm?) 13:18, 29 November 2015 (UTC)

WTF?

A whole section devoted to a card game, but no real description of the problem? And why C++ for implementation instead of pseudo-code or some more concise language? —Preceding unsigned comment added by 95.181.12.52 (talk) 14:02, 8 June 2010 (UTC)

I agree. There is too much explicit code for this article. It should be refactored into pseudocode. Resyst (talk) 16:11, 19 September 2015 (UTC)

Why is "Optimal" Marked as "?"

In the info box, there is a field "Optimal" that is marked "?" (note that this field isn't present in all sorting algorithms' info boxes). The worst case runtime for patience sort is O(nlogn), while the best case is O(n), which means it must be optimal in the general case due to the information theoretic lower-bound on comparison sorts.

Does optimal have some other meaning here, and if so, what is it, and can we make this field more descriptive?

Here is a quick survey of how optimal shows up in some other (comparison-based) sorting algorithms' info boxes:

• Bubble Sort: "Optimal : No"
  • in line with O(nlogn) worst case being optimal

• Insertion sort: "Optimal : No"
  • in line with O(nlogn) worst case being optimal

• Proportion extend sort: "Optimal : Yes"
  • in line with O(nlogn) worst case being optimal
  • note that this has a best-case of O(nlogn) also, whereas the lower bound for best case is O(n), which patience sort matches

• Quicksort: "Optimal : No"
  • in line with O(nlogn) worst case being optimal, since the unrandomized version is O(n^2) worst case

• Heapsort: Nothing listed

• Smoothsort: "Optimal : When the data is already sorted"
  • This one is very odd to me, since the worst case is O(nlogn) and the best case is O(n).

• Tree sort: "Optimal : Yes, if balanced"
  • Also in line with O(nlogn) worst case being optimal, as if the input is not balanced, the runtime is O(n^2), but if it is, the runtime is O(nlogn). Best case performance is O(nlogn), so it doesn't match the idea of "optimal" being optimal worst case and optimal best case.

• Library sort: "Optimal : ?"
  • This has a worst case O(n^2), but the "?" could be interpreted as "we don't know if there is an O(nlogn) version of this algorithm" (I don't know if this is actually an open question, I had never heard of this before today and didn't look into the algorithm). But for patience sorting, we do know there isn't a o(nlogn) algorithm for patience sorting due to the information theoretic lower bound.

• Cycle sort: "Optimal : Yes, in terms of the total number of writes to the original array"
  • This one is a totally different version of optimality, since it is inplace. The runtime is O(n^2), but it is optimal in the number of writes to the input, which is not the same as the standard definition of "optimal" for runtime complexity.

The other sorts either have nothing listed, or are in line with Optimal meaning "O(nlogn) worst case".

So, I propose marking this as "Optimal : Yes" or just removing this field altogether from sorting algorithms since it is redundant when the worst-case runtime is in the info box. For Cycle sort, the intro paragraph explains this version of optimality, so I think it is not helpful in that info box either.

When I read "Optimal : ?" I think that the (non)optimality is unknown (which again is not the case for patience sort). If this is what is intended, then just writing "Optimal : unknown" would be more clear, imo.

Zxcmc (talk) 01:47, 28 June 2026 (UTC)