sorts.iterative_merge_sort

Implementation of iterative merge sort in Python Author: Aman Gupta

For doctests run following command: python3 -m doctest -v iterative_merge_sort.py

For manual testing run: python3 iterative_merge_sort.py

Attributes

user_input

Classes

Comparable

Base class for protocol classes.

Functions

iter_merge_sort(→ list[T])	Return a sorted copy of the input list
merge(→ list[T])	sorting left-half and right-half individually

Module Contents

class sorts.iterative_merge_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.iterative_merge_sort.iter_merge_sort[T: Comparable](input_list: list[T]) → list[T]

Return a sorted copy of the input list

>>> iter_merge_sort([5, 9, 8, 7, 1, 2, 7])
[1, 2, 5, 7, 7, 8, 9]
>>> iter_merge_sort([1])
[1]
>>> iter_merge_sort([2, 1])
[1, 2]
>>> iter_merge_sort([2, 1, 3])
[1, 2, 3]
>>> iter_merge_sort([4, 3, 2, 1])
[1, 2, 3, 4]
>>> iter_merge_sort([5, 4, 3, 2, 1])
[1, 2, 3, 4, 5]
>>> iter_merge_sort(['c', 'b', 'a'])
['a', 'b', 'c']
>>> iter_merge_sort([0.3, 0.2, 0.1])
[0.1, 0.2, 0.3]
>>> iter_merge_sort(['dep', 'dang', 'trai'])
['dang', 'dep', 'trai']
>>> iter_merge_sort([6])
[6]
>>> iter_merge_sort([])
[]
>>> iter_merge_sort([-2, -9, -1, -4])
[-9, -4, -2, -1]
>>> iter_merge_sort([1.1, 1, 0.0, -1, -1.1])
[-1.1, -1, 0.0, 1, 1.1]
>>> iter_merge_sort(['c', 'b', 'a'])
['a', 'b', 'c']
>>> iter_merge_sort(list('cba'))
['a', 'b', 'c']
>>> iter_merge_sort([1, "a"])
Traceback (most recent call last):
...
TypeError: ...

sorts.iterative_merge_sort.merge[T: Comparable](input_list: list[T], low: int, mid: int, high: int) → list[T]

sorting left-half and right-half individually then merging them into result

sorts.iterative_merge_sort.user_input