sorts.merge_insertion_sort
==========================

.. py:module:: sorts.merge_insertion_sort

.. autoapi-nested-parse::

   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
----------

.. autoapisummary::

   sorts.merge_insertion_sort.user_input


Functions
---------

.. autoapisummary::

   sorts.merge_insertion_sort.binary_search_insertion
   sorts.merge_insertion_sort.merge
   sorts.merge_insertion_sort.merge_insertion_sort
   sorts.merge_insertion_sort.sortlist_2d


Module Contents
---------------

.. py:function:: binary_search_insertion(sorted_list, item)

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


.. py:function:: merge(left, right)

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


.. py:function:: merge_insertion_sort(collection: list[int]) -> list[int]

   Pure implementation of merge-insertion sort algorithm in Python

   :param 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


.. py:function:: sortlist_2d(list_2d)

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


.. py:data:: user_input