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]
(collection: list)
| 29 | |
| 30 | |
| 31 | def patience_sort(collection: list) -> list: |
| 32 | """A pure implementation of patience sort algorithm in Python |
| 33 | |
| 34 | :param collection: some mutable ordered collection with heterogeneous |
| 35 | comparable items inside |
| 36 | :return: the same collection ordered by ascending |
| 37 | |
| 38 | Examples: |
| 39 | >>> patience_sort([1, 9, 5, 21, 17, 6]) |
| 40 | [1, 5, 6, 9, 17, 21] |
| 41 | |
| 42 | >>> patience_sort([]) |
| 43 | [] |
| 44 | |
| 45 | >>> patience_sort([-3, -17, -48]) |
| 46 | [-48, -17, -3] |
| 47 | """ |
| 48 | stacks: list[Stack] = [] |
| 49 | # sort into stacks |
| 50 | for element in collection: |
| 51 | new_stacks = Stack([element]) |
| 52 | i = bisect_left(stacks, new_stacks) |
| 53 | if i != len(stacks): |
| 54 | stacks[i].append(element) |
| 55 | else: |
| 56 | stacks.append(new_stacks) |
| 57 | |
| 58 | # use a heap-based merge to merge stack efficiently |
| 59 | collection[:] = merge(*(reversed(stack) for stack in stacks)) |
| 60 | return collection |
| 61 | |
| 62 | |
| 63 | if __name__ == "__main__": |
no test coverage detected