merge_sort.py

X = [9, 3, 1, 10, 3, 2, 8, 6, 4, 5, 0]

def merge(L, R):
	A = []
	i, j = 0, 0
	
	while i < len(L) and j < len(R):
		if L[i] < R[j]:
			A.append(L[i])
			i = i + 1
		else:
			A.append(R[j])
			j = j + 1
			
	A += L[i:]
	A += R[j:]
	
	return A

def merge_sort(A):
	if len(A) <= 1:
		return A
	
	m = int(len(A) / 2)
	L = merge_sort(A[:m])
	R = merge_sort(A[m:])
	
	return merge(L, R)
	
print merge_sort(X)