According to Wikipedia (link), patience sort finds the longest increasing subsequence of a given sequence. Lets say the longest increasing subsequence of seq has length
Patience sort works like this:
Parameters: A sequence of integers called seq Output: A number between 0 and the length of seq. Lets call it patienceSort(seq) Algorithm (in Python): def patienceSort(seq): piles =  for el in seq: for i in range(len(piles)): # If there is a pile with a strictly greater element on top, # place current element on that pile if piles[i][-1] > el: piles[i].append(el) break # if there is no such pile, create a new one else: piles.append([el]) return len(piles)
What I've understood:
(I) We can guarantee that at every time the top of piles (
piles[i][-1]) is ordered in increasing order.
(II) For numbers in the same pile: Numbers are ordered...
(II.1) ... by time (first one in the pile came first)
(II.2) ... by value (first one in the pile has highest value)
(III) The numbers on top of the piles are not necessarily an increasing sequence within seq
(IV) The right pile is always the latest one that was created
Example for (III):
37 20 38 30 39 40 40 50 70 pile1 pile2 seq = [50,40,70,30,40, 39,38,37,20] [20,37] is not an increasing sequence in seq
For each card (which is not on the first pile), you can store a pointer to the top of the pile before when you add it to the pile. This way, you can get an increasing sequence by following the pointers and inverting the list. So:
patienceSort(seq) <= correct(seq)
patienceSort(seq) >= correct(seq)