import random
import time
def getRandomList(n,a,b):
    result = []
    for i in range(n):
        result.append(random.randint(a,b))
    return result

def mergesortH(A,b,e):
    if e-b > 1:
        mid = b + (e-b)//2
        mergesortH(A,b,mid)
        mergesortH(A,mid,e)
        #now merge
        i = b
        j = mid
        sortedList = []
        while i < mid and j < e:
            if A[i] <= A[j]:
                sortedList.append(A[i])
                i += 1
            else:
                sortedList.append(A[j])
                j += 1
        while i < mid:
            sortedList.append(A[i])
            i += 1
        while j < e:
            sortedList.append(A[j])
            j += 1
        k = 0
        for i in range(b,e):
            A[i] = sortedList[k]
            k = k + 1
        

def mergesort(A):
    mergesortH(A,0,len(A))

def isSorted(A):
    for i in range(len(A)-1):
        if A[i] > A[i+1]:

            return False
    return True

A =  getRandomList(8000,20,100)
#print A
start = time.time()
mergesort(A)
#print A
end = time.time()
print (isSorted(A))
print (end - start)