this is a pure python implementation of the mergeinsertion sort algorithm source https en wikipedia orgwikimergeinsertionsort for doctests run following command python3 m doctest v mergeinsertionsort py or python m doctest v mergeinsertionsort py for manual testing run python3 mergeinsertionsort py binarysearchinsertion1 2 7 9 10 4 1 2 4 7 9 10 merge1 6 9 10 2 3 4 5 7 8 1 6 2 3 4 5 7 8 9 10 sortlist2d9 10 1 6 7 8 2 3 4 5 1 6 2 3 4 5 7 8 9 10 pure implementation of mergeinsertion sort algorithm in python param collection some mutable ordered collection with heterogeneous comparable items inside return the same collection ordered by ascending examples mergeinsertionsort0 5 3 2 2 0 2 2 3 5 mergeinsertionsort99 99 mergeinsertionsort2 5 45 45 5 2 testing with all permutations on range0 5 import itertools permutations listitertools permutations0 1 2 3 4 allmergeinsertionsortp 0 1 2 3 4 for p in permutations true group the items into two pairs and leave one element if there is a last odd item example 999 100 75 40 10000 999 100 75 40 leave 10000 sort twopairs in each groups example 999 100 75 40 100 999 40 75 sort twopairedlist example 100 999 40 75 40 75 100 999 40 100 is sure because it has already been sorted generate the sortedlist of them so that you can avoid unnecessary comparison example group0 group1 40 100 75 999 group0 group1 40 100 75 999 100 999 is sure because it has already been sorted put 999 in last of the sortedlist so that you can avoid unnecessary comparison example group0 group1 40 100 75 999 group0 group1 40 100 999 75 insert the last odd item left if there is example group0 group1 40 100 999 75 group0 group1 40 100 999 10000 75 insert the remaining items in this case 40 75 is sure because it has already been sorted therefore you only need to insert 75 into 100 999 10000 so that you can avoid unnecessary comparison example group0 group1 40 100 999 10000 you don t need to compare with this as 40 75 is already sure 75 40 75 100 999 10000 if lastodditem is inserted before the item s index you should forward index one more binary_search_insertion 1 2 7 9 10 4 1 2 4 7 9 10 merge 1 6 9 10 2 3 4 5 7 8 1 6 2 3 4 5 7 8 9 10 sortlist_2d 9 10 1 6 7 8 2 3 4 5 1 6 2 3 4 5 7 8 9 10 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 group the items into two pairs and leave one element if there is a last odd item example 999 100 75 40 10000 999 100 75 40 leave 10000 sort two pairs in each groups example 999 100 75 40 100 999 40 75 sort two_paired_list example 100 999 40 75 40 75 100 999 40 100 is sure because it has already been sorted generate the sorted_list of them so that you can avoid unnecessary comparison example group0 group1 40 100 75 999 group0 group1 40 100 75 999 100 999 is sure because it has already been sorted put 999 in last of the sorted_list so that you can avoid unnecessary comparison example group0 group1 40 100 75 999 group0 group1 40 100 999 75 insert the last odd item left if there is example group0 group1 40 100 999 75 group0 group1 40 100 999 10000 75 insert the remaining items in this case 40 75 is sure because it has already been sorted therefore you only need to insert 75 into 100 999 10000 so that you can avoid unnecessary comparison example group0 group1 40 100 999 10000 you don t need to compare with this as 40 75 is already sure 75 40 75 100 999 10000 if last_odd_item is inserted before the item s index you should forward index one more
from __future__ import annotations


def binary_search_insertion(sorted_list, item):
    
    left = 0
    right = len(sorted_list) - 1
    while left <= right:
        middle = (left + right) // 2
        if left == right:
            if sorted_list[middle] < item:
                left = middle + 1
            break
        elif sorted_list[middle] < item:
            left = middle + 1
        else:
            right = middle - 1
    sorted_list.insert(left, item)
    return sorted_list


def merge(left, right):
    
    result = []
    while left and right:
        if left[0][0] < right[0][0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    return result + left + right


def sortlist_2d(list_2d):
    
    length = len(list_2d)
    if length <= 1:
        return list_2d
    middle = length // 2
    return merge(sortlist_2d(list_2d[:middle]), sortlist_2d(list_2d[middle:]))


def merge_insertion_sort(collection: list[int]) -> list[int]:
    

    if len(collection) <= 1:
        return collection

    
    two_paired_list = []
    has_last_odd_item = False
    for i in range(0, len(collection), 2):
        if i == len(collection) - 1:
            has_last_odd_item = True
        else:
            
            if collection[i] < collection[i + 1]:
                two_paired_list.append([collection[i], collection[i + 1]])
            else:
                two_paired_list.append([collection[i + 1], collection[i]])

    
    sorted_list_2d = sortlist_2d(two_paired_list)

    
    result = [i[0] for i in sorted_list_2d]

    
    result.append(sorted_list_2d[-1][1])

    
    if has_last_odd_item:
        pivot = collection[-1]
        result = binary_search_insertion(result, pivot)

    
    is_last_odd_item_inserted_before_this_index = False
    for i in range(len(sorted_list_2d) - 1):
        if result[i] == collection[-1] and has_last_odd_item:
            is_last_odd_item_inserted_before_this_index = True
        pivot = sorted_list_2d[i][1]
        
        
        if is_last_odd_item_inserted_before_this_index:
            result = result[: i + 2] + binary_search_insertion(result[i + 2 :], pivot)
        else:
            result = result[: i + 1] + binary_search_insertion(result[i + 1 :], pivot)

    return result


if __name__ == "__main__":
    user_input = input("Enter numbers separated by a comma:\n").strip()
    unsorted = [int(item) for item in user_input.split(",")]
    print(merge_insertion_sort(unsorted))