'''
Created on Dec 1, 2010

@author: ola
'''

import random

def merge(left, right):
    result = []
    i ,j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result


def mergesort(list):
    if len(list) < 2:
        return list
    else:
        middle = len(list) / 2
        left = mergesort(list[:middle])
        right = mergesort(list[middle:])
        return merge(left, right)
    

def isSorted(lst):
    for i,n in enumerate(lst[1:]):
        if n < lst[i]:
            return False
    return True

nums = [x for x in range(0,100)]
random.shuffle(nums)
snums = mergesort(nums)

print isSorted(nums)
print isSorted(snums)

print nums
print snums