# In this version of Merge sort, instead of creating new lists,
# a constant work buffer is needed.

import timing   # only use on Unix/Linux systems
import time
import sys
from random import *

### mergesort for arrays, with constant work buffer: O(n) extra memory needed.

def copypart(M,N,s,e): # copy M[s:e] to same cells in N
    i = s
    while i<e and i<len(M) and i<len(N):
        N[i] = M[i]
        i += 1
#copypart

def mergesort(A):
    n = len(A)
    B = [0]*n   # work space array

    # the following is a local function, visible only inside mergesort
    def merge(s,m,e): #merge partitions A[s:m] and A[m:e] using B
        i = s  # indexes first partition
        j = m  # indexes second partition
        k = s  # indexes merged parition (in B)
        while i<m and j<e:
            if A[i]<A[j]:  # add A[i] into merged partition
                B[k] = A[i]
                i += 1
            else:  # add A[j] into merged parition
                B[k] = A[j]
                j += 1
            k += 1  
        # while
        ## when loop ends, one partition may still have leftovers:
        ii,mm = i,m   # indexes of partition that has leftovers
        if (j<e): ii,mm = j,e
        while ii<mm:  # copy over leftovers
            B[k] = A[ii]
            ii += 1
            k += 1
        #while ii
        copypart(B,A,s,e)  # copy merged partition back to A
    # merge

    def msort(s,e):  # main recursive procedure sorts A[s:e]
        if (e-s >= 2):  # else no sorting needed
            m = (e+s)/2  # midpoint
            msort(s,m)  # recursively sort first partition
            msort(m,e)  # sort second partition
            merge(s,m,e)  # merge sorted partition
    #msort

    msort(0,n)  # body of mergesort initiates call to msort            
#mergesort



###### bubblesort (optimized)  for comparison

def bubblesort(A):
    n = len(A)
    i, j = 0,0
    while i<n-1:  # note n-1
        j = 0
        while j<n-1-i:
            if A[j]>A[j+1]:
                A[j],A[j+1] = A[j+1],A[j]    # swap
            j +=1
        # while j
        i +=1
    # while i
## bubblesort


def sorted(A):  # function to check if array is sorted (to verify sorting)
    ax = True
    i = 0
    while i<len(A)-1 and ax:
        if A[i]>A[i+1]: ax = False
        i += 1
    return ax
## sorted

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

if len(sys.argv)>1:
    size = int(sys.argv[1])  # size of test array as command-line argument
else: size = 2000  # default size of random array

## generate random array
A=[0]*size
i = 0
while i<size:
    r = random()*100000
    A[i] = r
    i +=1
## loop to generate random array

# start timing experiment
timing.start()
mergesort(A)
#bubblesort(A)
timing.finish()
m1 = timing.milli()

if not(sorted(A)): 
    print "NOT SORTED!!"
else:
    print "time to sort:",m1,"ms"