#!/usr/bin/env python
#
# recursion
#
import random

size= 9
origarray= []
i = 0
while(i < size):
    x = random.random()
    origarray.append(int(1000* x))
    i+= 1
print(origarray)


# inputs: two sorted arrays (in ascending order)
# output: a single sorted array whose elements equal the elements of
# the two inputs
# side effects to global data structures: none
def merge(arr1, arr2):
    out=[]
    i=0
    j=0
    while ((i < (len(arr1))) | (j < (len(arr2)))):
        if (i == len(arr1)):
            out.append(arr2[j])
            j=j+1
        elif (j == len(arr2)):
            out.append(arr1[i])
            i=i+1
        elif (arr1[i] <= arr2[j]):
            out.append(arr1[i])
            i=i+1
        elif (arr1[i] > arr2[j]):
            out.append(arr2[j])
            j=j+1
        else:
            print("We should not be here")
    return out


# sort an array
# input: an array which is probably not sorted
# output: an array sorted in ascending order
# method: divide in two, call this function recursively on each half
# then merge.
def mergesort(arr):
    if(1 >= len(arr)):
        return arr
    else:
        x = len(arr)
        mid = int(x/2)
        return(merge(mergesort(arr[:mid]), mergesort(arr[mid:])))



print(mergesort(origarray))