Merge Sort Python Implementation

merge_sort.py

# Merge Sort -> Python implementation
# Time Complexity: O(nlogn)
# Space Complexity: O(n)

def merge_sort(array: list) -> list:
    def _merge(_array1: list, _array2: list) -> list:
        new_array = []
        ptr1 = ptr2 = 0

        while ptr1 < len(_array1) and ptr2 < len(_array2):
            if _array1[ptr1] < _array2[ptr2]:
                new_array.append(_array1[ptr1])
                ptr1 += 1
            else:
                new_array.append(_array2[ptr2])
                ptr2 += 1

        if ptr1 < len(_array1):
            new_array.extend(_array1[ptr1:])
        else:
            new_array.extend(_array2[ptr2:])

        return new_array

    def _merge_sort(_array: list) -> list:
        if len(_array) <= 1:
            return _array

        mid = len(_array) // 2

        arr1 = _merge_sort(_array[:mid])
        arr2 = _merge_sort(_array[mid:])

        return _merge(arr1, arr2)

    return _merge_sort(array)


if __name__ == '__main__':
    ans = merge_sort([2, 4, 9, 1, 8, 7, 3, 5, 6])
    print(ans)