sorts.recursive_mergesort_array

A merge sort which accepts comparable items and recursively splits them in half, then sorts and combines the halves.

https://en.wikipedia.org/wiki/Merge_sort

Classes

Comparable

Base class for protocol classes.

Functions

merge(→ list[T])

Return a new list of collection sorted in ascending order.

Module Contents

class sorts.recursive_mergesort_array.Comparable

Bases: Protocol

Base class for protocol classes.

Protocol classes are defined as:

class Proto(Protocol):
    def meth(self) -> int:
        ...

Such classes are primarily used with static type checkers that recognize structural subtyping (static duck-typing).

For example:

class C:
    def meth(self) -> int:
        return 0

def func(x: Proto) -> int:
    return x.meth()

func(C())  # Passes static type check

See PEP 544 for details. Protocol classes decorated with @typing.runtime_checkable act as simple-minded runtime protocols that check only the presence of given attributes, ignoring their type signatures. Protocol classes can be generic, they are defined as:

class GenProto[T](Protocol):
    def meth(self) -> T:
        ...

__lt__(other: object, /) → bool

sorts.recursive_mergesort_array.merge[T: Comparable](collection: collections.abc.Iterable[T]) → list[T]

Return a new list of collection sorted in ascending order.

The input is copied, so the original iterable is left unchanged. Items must be mutually comparable with <.

>>> merge([10,9,8,7,6,5,4,3,2,1])
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> merge([1,2,3,4,5,6,7,8,9,10])
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> merge([10,22,1,2,3,9,15,23])
[1, 2, 3, 9, 10, 15, 22, 23]
>>> merge([100])
[100]
>>> merge([])
[]
>>> merge(["c", "a", "b"])
['a', 'b', 'c']
>>> merge([2.5, -1, 0.0])
[-1, 0.0, 2.5]
>>> values = [3, 1, 2]
>>> merge(values)
[1, 2, 3]
>>> values
[3, 1, 2]
>>> merge(("b", "c", "a"))
['a', 'b', 'c']
>>> merge([1, "a"])
Traceback (most recent call last):
    ...
TypeError: '<' not supported between instances of 'int' and 'str'