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 correct(seq)Patience sort works like this:Parameters: A sequence of integers called seqOutput: 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 createdExample for (III):      3720    3830    3940    4050    70pile1 pile2seq = [50,40,70,30,40, 39,38,37,20][20,37] is not an increasing sequence in seqFor 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)QuestionWhy is patienceSort(seq) >= correct(seq) 
Why does Patience sorting find the longest increasing subsequence?
algorithms