merge_sort.py

INF = float('inf')


def merge(A, p, q, r):
    L = A[p:q + 1]
    R = A[q + 1:r + 1]
    L.append(INF)
    R.append(INF)
    i = j = 0
    for k in range(p, r + 1):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1


def merge_sort(A, p, r):
    if p < r:
        q = (p + r) // 2
        merge_sort(A, p, q)
        merge_sort(A, q + 1, r)
        merge(A, p, q, r)


def main():
    a = [3, 41, 52, 26, 38, 57, 9, 49, 5]
    print("source array={}".format(a))
    merge_sort(a, 0, len(a) - 1)
    print("sorted array={0}".format(a))


if __name__ == "__main__":
    main()