helper function for mergesort lefthalf 2 righthalf 1 mergelefthalf righthalf 2 1 lefthalf 1 2 3 righthalf 4 5 6 mergelefthalf righthalf 1 2 3 4 5 6 lefthalf 2 righthalf 1 mergelefthalf righthalf 2 1 lefthalf 12 15 righthalf 13 14 mergelefthalf righthalf 12 13 14 15 lefthalf righthalf mergelefthalf righthalf returns a list of sorted array elements using merge sort from random import shuffle array 2 3 10 11 99 100000 100 200 shufflearray mergesortarray 200 10 2 3 11 99 100 100000 shufflearray mergesortarray 200 10 2 3 11 99 100 100000 array 200 mergesortarray 200 array 2 3 10 11 99 100000 100 200 shufflearray sortedarray mergesortarray true array 2 mergesortarray 2 array mergesortarray array 10000000 1 1111111111 101111111112 9000002 sortedarray mergesortarray true the actual formula to calculate the middle element left right left 2 this avoids integer overflow in case of large n split the array into halves till the array length becomes equal to one merge the arrays of single length returned by mergesort function and pass them into the merge arrays function which merges the array helper function for mergesort left_half 2 right_half 1 merge left_half right_half 2 1 left_half 1 2 3 right_half 4 5 6 merge left_half right_half 1 2 3 4 5 6 left_half 2 right_half 1 merge left_half right_half 2 1 left_half 12 15 right_half 13 14 merge left_half right_half 12 13 14 15 left_half right_half merge left_half right_half pointer to current index for left half pointer to current index for the right half pointer to current index for the sorted array half returns a list of sorted array elements using merge sort from random import shuffle array 2 3 10 11 99 100000 100 200 shuffle array merge_sort array 200 10 2 3 11 99 100 100000 shuffle array merge_sort array 200 10 2 3 11 99 100 100000 array 200 merge_sort array 200 array 2 3 10 11 99 100000 100 200 shuffle array sorted array merge_sort array true array 2 merge_sort array 2 array merge_sort array array 10000000 1 1111111111 101111111112 9000002 sorted array merge_sort array true the actual formula to calculate the middle element left right left 2 this avoids integer overflow in case of large n split the array into halves till the array length becomes equal to one merge the arrays of single length returned by mergesort function and pass them into the merge arrays function which merges the array
from __future__ import annotations


def merge(left_half: list, right_half: list) -> list:
    
    sorted_array = [None] * (len(right_half) + len(left_half))

    pointer1 = 0  
    pointer2 = 0  
    index = 0  

    while pointer1 < len(left_half) and pointer2 < len(right_half):
        if left_half[pointer1] < right_half[pointer2]:
            sorted_array[index] = left_half[pointer1]
            pointer1 += 1
            index += 1
        else:
            sorted_array[index] = right_half[pointer2]
            pointer2 += 1
            index += 1
    while pointer1 < len(left_half):
        sorted_array[index] = left_half[pointer1]
        pointer1 += 1
        index += 1

    while pointer2 < len(right_half):
        sorted_array[index] = right_half[pointer2]
        pointer2 += 1
        index += 1

    return sorted_array


def merge_sort(array: list) -> list:
    
    if len(array) <= 1:
        return array
    
    
    middle = 0 + (len(array) - 0) // 2

    
    
    
    left_half = array[:middle]
    right_half = array[middle:]

    return merge(merge_sort(left_half), merge_sort(right_half))


if __name__ == "__main__":
    import doctest

    doctest.testmod()