import numpy
import time
import math

def merge_sort(A, p, r):
    if p < r:
        q = math.floor( 0.5 * (p+r) )
        merge_sort(A, p, q)
        merge_sort(A, q + 1, r)
        merge(A, p, q, r)


def merge(A, p, q, r):
    n1 = q - p + 1
    n2 = r - q
    L = numpy.zeros(n1 + 1)
    R = numpy.zeros(n2 + 1)
    # print (n1)
    # print (n2)
    for i in range(n1):
        L[i] = A[p + i]
    for j in range(n2):
        R[j] = A[q + j + 1]
    L[n1] = R[n2] = 1000
    i = 0
    j = 0
    # print(L)
    # print(R)
    for k in range(p, r+1):
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1


def sort_with_time(A):
    st = time.clock()
    merge_sort(A, 0, len(A)-1)
    et = time.clock()
    return et - st


def time_sort(n):
    print (n)
    x = numpy.random.uniform(size = n)
    return sort_with_time(x)