#!/usr/local/bin/python3
# Author: Dr. Robert Heckendorn, Computer Science Department, University of Idaho, 2013
def merge(x) :
    return mergeaux(x, 0, len(x))

def mergeaux(x, start, end) :
    print((start, end))
    if end-start<=1 :
        # return the list of one item
        print("x")
        return [x[start]]
    else:
        pivot = ((end-1)+start)//2

        # sort left and right halves
        left = mergeaux(x, start, pivot+1)
        right = mergeaux(x, pivot+1, end)

        # merge the results until one list is empty
        l = 0
        r = 0
        ans = []
        while l<len(left) and r<len(right) :
            if left[l]<right[r] :
                print("x")
                ans.append(left[l])
                l+=1
            else :
                print("x")
                ans.append(right[r])
                r+=1

        # tack on remaining elements
        for i in range(l, len(left)) :
            print("x")
            ans.append(left[i])
        for i in range(r, len(right)) :
            print("x")
            ans.append(right[i])
            
        return ans

y = [3, 2, 5, 1]
y = [31, 41, 59, 26, 53, 58, 97, 93, 23, 84, 62, 64, 33, 83, 27, 9, 50, 28, 8, 41, 97, 1, 69, 3, 99, 37, 5, 10]
print(len(y))
# y = merge(y)
y = merge(y + y)
print("sorted:" , y)