sorts.merge_insertion_sort

This is a pure Python implementation of the merge-insertion sort algorithm Source: https://en.wikipedia.org/wiki/Merge-insertion_sort

For doctests run following command: python3 -m doctest -v merge_insertion_sort.py or python -m doctest -v merge_insertion_sort.py

For manual testing run: python3 merge_insertion_sort.py

Attributes

user_input

Classes

Comparable

Base class for protocol classes.

Functions

binary_search_insertion(→ list[T])
merge(→ list[list[T]])
merge_insertion_sort(→ list[T])	Pure implementation of merge-insertion sort algorithm in Python
sortlist_2d(→ list[list[T]])

Module Contents

class sorts.merge_insertion_sort.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: Any, /) → bool

sorts.merge_insertion_sort.binary_search_insertion[T: Comparable](sorted_list: list[T], item: T) → list[T]

>>> binary_search_insertion([1, 2, 7, 9, 10], 4)
[1, 2, 4, 7, 9, 10]

sorts.merge_insertion_sort.merge[T: Comparable](left: list[list[T]], right: list[list[T]]) → list[list[T]]

>>> merge([[1, 6], [9, 10]], [[2, 3], [4, 5], [7, 8]])
[[1, 6], [2, 3], [4, 5], [7, 8], [9, 10]]

sorts.merge_insertion_sort.merge_insertion_sort[T: Comparable](collection: list[T]) → list[T]

Pure implementation of merge-insertion sort algorithm in Python

Parameters:

collection – some mutable ordered collection with heterogeneous

comparable items inside :return: the same collection ordered by ascending

Examples: >>> merge_insertion_sort([0, 5, 3, 2, 2]) [0, 2, 2, 3, 5]

>>> merge_insertion_sort([99])
[99]

>>> merge_insertion_sort([-2, -5, -45])
[-45, -5, -2]

Testing with all permutations on range(0,5): >>> import itertools >>> permutations = list(itertools.permutations([0, 1, 2, 3, 4])) >>> all(merge_insertion_sort(p) == [0, 1, 2, 3, 4] for p in permutations) True

sorts.merge_insertion_sort.sortlist_2d[T: Comparable](list_2d: list[list[T]]) → list[list[T]]

>>> sortlist_2d([[9, 10], [1, 6], [7, 8], [2, 3], [4, 5]])
[[1, 6], [2, 3], [4, 5], [7, 8], [9, 10]]

sorts.merge_insertion_sort.user_input