import timeit
import random # will not be needed in binary search

# MERGE (A, p, q, r)
def Merge(A, p, q, r):
    L = A[p : q]
    R = A[q : r]
    i, j = 0, 0
    for k in range(p, r):
        if(i < len(L) and j < len(R)):
            if(L[i] <= R[j]):
                A[k] = L[i]
                i += 1
            else:
                A[k] = R[j]
                j += 1
        elif(i < len(L) and j >= len(R)):
            A[k] = L[i]
            i += 1
        elif(i >= len(L) and j < len(R)):
            A[k] = R[j]
            j += 1

# MERGE SORT (A, p, r)
def MergeSort(A, p, r):
    # if p < r
    if p < r:
        # q = (p + r) / 2
        q = (p + r) / 2
        # MERGE SORT (A, p, q)
        MergeSort(A, p, q)
        # MERGE SORT (A, q + 1, r)
        MergeSort(A, q + 1, r)
        # MERGE (A, p, q, r)
        Merge(A, p, q, r)

A = [x for x in range(1000)]
random.shuffle(A) # will not be needed in binary search
t = timeit.Timer('MergeSort(A, 0, len(A))', 'from __main__ import MergeSort, A')
time = (1000000 * t.timeit(number = 1)) # micro-seconds
print "MergeSort(10**3) takes %0.3f micro-seconds" % time