Basic Merge Sort

MergeSort.py

from typing import List, Tuple

def merge_sort(arr: List):

    # Sort and Merge
    def merge(first: Tuple, second: Tuple) -> Tuple:

        # Init
        a, n = first
        b, m = second
        i, j = 0, 0
        res = []

        # Sort
        while i < n and j < m:
            if a[i] < b[j]:
                res.append(a[i])
                i += 1
            elif a[i] > b[j]:
                res.append(b[j])
                j += 1
            else:
                res.append(a[i])
                i += 1
                res.append(b[j])
                j += 1
        while i < n:
            res.append(a[i])
            i += 1
        while j < m:
            res.append(b[j])
            j += 1

        return (res, m+n)

    # Partition, Sort and Merge
    def sort(arr: List, low: int, high: int) -> Tuple:
        if low < high:
            mid = low + ((high - low) // 2)
            return merge(sort(arr, low, mid), sort(arr, mid+1, high)) 
        else:
            return ([arr[low]], 1)

    return sort(arr, 0, len(arr)-1)[0]

a = [4,1,3,0,5,2,7,9]
print(merge_sort(a))