this is a pure python implementation of the merge sort algorithm for doctests run following command python m doctest v mergesort py or python3 m doctest v mergesort py for manual testing run python mergesort py sorts a list using the merge sort algorithm param collection a mutable ordered collection with comparable items return the same collection ordered in ascending order time complexity on log n examples mergesort0 5 3 2 2 0 2 2 3 5 mergesort mergesort2 5 45 45 5 2 merge two sorted lists into a single sorted list param left left collection param right right collection return merged result sorts a list using the merge sort algorithm param collection a mutable ordered collection with comparable items return the same collection ordered in ascending order time complexity o n log n examples merge_sort 0 5 3 2 2 0 2 2 3 5 merge_sort merge_sort 2 5 45 45 5 2 merge two sorted lists into a single sorted list param left left collection param right right collection return merged result
def merge_sort(collection: list) -> list:
    

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

    if len(collection) <= 1:
        return collection
    mid_index = len(collection) // 2
    return merge(merge_sort(collection[:mid_index]), merge_sort(collection[mid_index:]))


if __name__ == "__main__":
    import doctest

    doctest.testmod()

    try:
        user_input = input("Enter numbers separated by a comma:\n").strip()
        unsorted = [int(item) for item in user_input.split(",")]
        sorted_list = merge_sort(unsorted)
        print(*sorted_list, sep=",")
    except ValueError:
        print("Invalid input. Please enter valid integers separated by commas.")