def merge_sort(arr):
    """
    time complexity: O(n*logn)
    space complexity: O(n)
    :prarm arr: list
    :return: list
    """
    if not isinstance(arr, list):
        raise TypeError
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    k, i, j = 0, 0, 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
        k += 1
    if i < len(left):
        arr[k:] = left[i:]
    if j < len(right):
        arr[k:] = right[j:]
    return arr