a merge sort which accepts an array as input and recursively splits an array in half and sorts and combines them https en wikipedia orgwikimergesort def mergearr listint listint if lenarr 1 middlelength lenarr 2 finds the middle of the array leftarray arr middlelength creates an array of the elements in the first half rightarray arr middlelength creates an array of the elements in the second half leftsize lenleftarray rightsize lenrightarray mergeleftarray starts sorting the left mergerightarray starts sorting the right leftindex 0 left counter rightindex 0 right counter index 0 position counter while leftindex leftsize and rightindex rightsize runs until the lowers size of the left and right are sorted if leftarrayleftindex rightarrayrightindex arrindex leftarrayleftindex leftindex 1 else arrindex rightarrayrightindex rightindex 1 index 1 while leftindex leftsize adds the left over elements in the left half of the array arrindex leftarrayleftindex leftindex 1 index 1 while rightindex rightsize adds the left over elements in the right half of the array arrindex rightarrayrightindex rightindex 1 index 1 return arr if name main import doctest doctest testmod https en wikipedia org wiki merge_sort return a sorted array merge 10 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10 merge 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 merge 10 22 1 2 3 9 15 23 1 2 3 9 10 15 22 23 merge 100 100 merge finds the middle of the array creates an array of the elements in the first half creates an array of the elements in the second half starts sorting the left starts sorting the right left counter right counter position counter runs until the lowers size of the left and right are sorted adds the left over elements in the left half of the array adds the left over elements in the right half of the array
def merge(arr: list[int]) -> list[int]:
    
    if len(arr) > 1:
        middle_length = len(arr) // 2  
        left_array = arr[
            :middle_length
        ]  
        right_array = arr[
            middle_length:
        ]  
        left_size = len(left_array)
        right_size = len(right_array)
        merge(left_array)  
        merge(right_array)  
        left_index = 0  
        right_index = 0  
        index = 0  
        while (
            left_index < left_size and right_index < right_size
        ):  
            if left_array[left_index] < right_array[right_index]:
                arr[index] = left_array[left_index]
                left_index += 1
            else:
                arr[index] = right_array[right_index]
                right_index += 1
            index += 1
        while (
            left_index < left_size
        ):  
            arr[index] = left_array[left_index]
            left_index += 1
            index += 1
        while (
            right_index < right_size
        ):  
            arr[index] = right_array[right_index]
            right_index += 1
            index += 1
    return arr


if __name__ == "__main__":
    import doctest

    doctest.testmod()