import time
from random import *

# Merge Sort
def mergeSort(n, s):
    h=int(n/2)
    m=n-h


    if(n>1):
        leftHalf=s[:h]
        rightHalf=s[h:]
        mergeSort(h,leftHalf)
        mergeSort(m,rightHalf)
        merge(h,m,leftHalf,rightHalf,s)

# merge
def merge(h,m,u,v,s):
    i=j=k=0
    while(i<=h-1 and j<=m-1):
        if(u[i]<v[j]):
           s[k]=u[i]
           i+=1
        else:
           s[k]=v[j]
           j+=1
        k+=1
    if(i>h-1):
           for ii in range (j,m):
                s[k]=v[ii]
                k += 1
    else:
           for ii in range (i,h):
              s[k]=u[ii]
              k += 1

# Exchange Sort
def exchangeSort(n,s) :
    for i in range(n-1) :
        j = i+1
        while j <= n-1 :
            if s[i] > s[j] :
                temp = s[i]
                s[i] = s[j]
                s[j] = temp
            j += 1


# time check function
# sort_type : merge / exchange
# s : random data set
def functionTimeCheck(sort_type, s) :
    
    if sort_type == "merge" : 
        stime = time.time()
        mergeSort(len(s),s)
        print('merge sort    : %10.5f' % (time.time()-stime))
    elif sort_type == "exchange" :
        stime = time.time()
        exchangeSort(len(s),s)
        print('exchange sort : %10.5f' % (time.time()-stime))
    else :
        print("invalid input")


# create random set
n = input("Problem Scale : ")
s = []
for i in range(n) :
    rand_value = randint(0,1000)
    s.append(rand_value)

functionTimeCheck("merge",s)
functionTimeCheck("exchange",s)