# mergesort as a good example of recursion:
from random import random, randint
import time
import sys

def mergesort(A):
   B = [0]*len(A)  # work space
   
   def msort(start,end):  # sort from start to end-1
       if end-start<2: return  # one element partition do nothing: base case
       mid = (start+end)//2  # middle index
       msort(start,mid)  # recursively sort left partition
       msort(mid,end)    # and right partition
       merge(start,mid,end) # merge the two sorted partitions into one parition
   #msort

   def merge(start,mid,end):
       i = start # indexes left partition
       j = mid   # indexes right partition
       k = start # indexes work space B
       while (i<mid and j<end):
           if A[i]<A[j]:
               B[k] = A[i]
               i += 1
           else:
               B[k] = A[j]
               j += 1
           k += 1
       #while, at this point, there still may be leftovers on left partition:
       while i<mid:
           B[k]=A[i]
           k += 1
           i += 1
       #while i<mid: right partition values don't need to be copied
       # Now copy B back into A:
       while k>start:
           A[k-1] = B[k-1]
           k -=1
       #while k>start, remainder in B don't need to be copied
   # inner merge function

   msort(0,len(A))  # main body of mergesort
#mergesort

"""
A = [4,5,1,9,3,8,2,7,6,0]
mergesort(A)
print(A)
"""

#### swapsort in comparison
def swapsort(A):
    for i in range(0,len(A)-1):
        mi = i  # index of smallest starting from index i
        for k in range(i,len(A)):
            if A[k]<A[mi]: mi = k
        A[i],A[mi] = A[mi],A[i] # swap smallest to position i
#swapsort


def sorted(A):  # check sorted
    answer = True
    i = 0
    while i<len(A)-1 and answer:
        if A[i]>A[i+1]: answer = False
        i +=1
    return answer
# sorted

### dispatch vector of sorting procedures:
SORTALG = [mergesort, swapsort]
si = 0  # indexes SORTALG

n = 10000  # size of test array
if len(sys.argv)>1: n = int(sys.argv[1])
if len(sys.argv)>2: si = int(sys.argv[2])

A = [0]*n
for i in range(0,n):
    A[i] = randint(0,n*n)

t1 = time.time()
SORTALG[si%len(SORTALG)](A)
t2 = time.time()

if not(sorted(A)): print("sorting did not work")
else: print("sorted in "+str(t2-t1)+" sec.")

"""
Mergesort has (worst-case) time complexity in n*log(n) while swapsort is in
n*n.  Experimentally, you will see that, when the length of an array doubles,
the time to mergesort the array will just slightly more than double, while
the time to swapsort will quadruple.  n*log(n) is also called 'quazi-linear'.
"""