a pure python implementation of the patience sort algorithm for more information https en wikipedia orgwikipatiencesorting this algorithm is based on the card game patience for doctests run following command python3 m doctest v patiencesort py for manual testing run python3 patiencesort py a pure implementation of patience sort algorithm in python param collection some mutable ordered collection with heterogeneous comparable items inside return the same collection ordered by ascending examples patiencesort1 9 5 21 17 6 1 5 6 9 17 21 patiencesort patiencesort3 17 48 48 17 3 sort into stacks use a heapbased merge to merge stack efficiently a pure python implementation of the patience sort algorithm for more information https en wikipedia org wiki patience_sorting this algorithm is based on the card game patience for doctests run following command python3 m doctest v patience_sort py for manual testing run python3 patience_sort py a pure implementation of patience sort algorithm in python param collection some mutable ordered collection with heterogeneous comparable items inside return the same collection ordered by ascending examples patience_sort 1 9 5 21 17 6 1 5 6 9 17 21 patience_sort patience_sort 3 17 48 48 17 3 sort into stacks use a heap based merge to merge stack efficiently
from __future__ import annotations

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: list[Stack] = []
    
    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)

    
    collection[:] = merge(*(reversed(stack) for stack in stacks))
    return collection


if __name__ == "__main__":
    user_input = input("Enter numbers separated by a comma:\n").strip()
    unsorted = [int(item) for item in user_input.split(",")]
    print(patience_sort(unsorted))