#coding:utf-8

def merge_sort(array):

	length = len(array)

	if length <= 1: return array

	m = length / 2

	left = array[:m]

	right = array[m:]

	left = merge_sort(left)

	right = merge_sort(right)

	return merge(left,right)

def merge(left,right):

	result = []

	while len(left)>0 and len(right)>0 :

		if left[0] <= right[0]:

			result.append(left.pop(0))

		else:

			result.append(right.pop(0))

	result.extend(left)

	result.extend(right)

	return result

if __name__ == '__main__':

	print merge_sort([33,11,2,3,7,2234234234234234,4,23,2,3,4,7])

	print merge_sort([0,1,2,3,4,5,5,6,7,8,9])

	print merge_sort([9,8,7,6,5,5,4,3,2,1,0])