空间复杂度为O(1)的归并排序

def cmp(left, mid):
    return left > mid


def merge(arr, left, mid, right):
    while mid < right:
        for move_left in range(left, mid):
            if cmp(arr[move_left], arr[mid]):
                tmp = arr[move_left]
                for i in range(move_left, mid):
                    arr[move_left] = arr[i + 1]
                    arr[i + 1] = tmp
                    tmp = arr[move_left]
                left = move_left
                break
        mid += 1


def merge_sort(arr, l=None, r=None):
    if l is None:
        l = 0
    if r is None:
        r = len(arr)
    if l == r -1:
        return arr
    else:
        mid = int((l + r) / 2)
        merge_sort(arr, l, mid)
        merge_sort(arr, mid + 1, r)
        merge(arr, l, mid, r)


if __name__ == '__main__':
    arr = [12, 2, 3]
    merge_sort(arr)

    print(arr)