Python: Sort unsorted numbers using Patience sorting

Last update on January 06 2025 13:30:47 (UTC/GMT +8 hours)

Write a Python program to sort unsorted numbers using patience sorting.

From Wikipedia:
In computer science, patience sorting is a sorting algorithm inspired by, and named after, the card game patience. A variant of the algorithm efficiently computes the length of a longest increasing subsequence in a given array.
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.
1. nitially, there are no piles. The first card dealt forms a new pile consisting of the single card.
2. 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.
3. When there are no more cards remaining to deal, the game ends.

Sample Solution:

Python Code:

#Ref.https://bit.ly/2YiegZB
from bisect import bisect_left
from functools import total_ordering
from heapq import merge
@total_ordering
class Stack(list):
    def __lt__(self, other):
        return self[-1] < other[-1]
    def __eq__(self, other):
        return self[-1] == other[-1]
def patience_sort(collection: list) -> list:
    stacks = []
    # sort into stacks
    for element in collection:
        new_stacks = Stack([element])
        i = bisect_left(stacks, new_stacks)
        if i != len(stacks):
            stacks[i].append(element)
        else:
            stacks.append(new_stacks)

    # use a heap-based merge to merge stack efficiently
    collection[:] = merge(*[reversed(stack) for stack in stacks])
    return collection            
nums = [4, 3, 5, 1, 2]
print("\nOriginal list:")
print(nums)
patience_sort(nums)
print("Sorted order is:", nums)
nums = [5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
print("\nOriginal list:")
print(nums)
patience_sort(nums)
print("Sorted order is:", nums)

Sample Output:

Original list:
[4, 3, 5, 1, 2]
Sorted order is: [1, 2, 3, 4, 5]

Original list:
[5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
Sorted order is: [-18, -4, 0, 3, 5, 5, 7, 9, 10, 46, 92, 178]

Flowchart:

Python Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Python program to sort unsorted numbers using Pigeonhole sorting.
Next: Write a Python program to sort an odd–even sort or odd–even transposition sort.