Mergesort

merge_sort.py

def merge(left,right):
	result = []
	while len(left) > 0 and len(right) > 0:
		if left[0] < right[0]:
			result.append(left[0])
			left = left[1:]
		else:
			result.append(right[0])
			right = right[1:]
	if len(left)  > 0:
		result.extend(left)
	elif len(right) > 0:
		result.extend(right)
	return result
	
def merge_sort(arr):
	if len(arr) <= 1:
		return arr
	mid = len(arr) // 2
	left = arr[:mid]
	right = arr[mid:]
	left = merge_sort(left)
	right = merge_sort(right)
	return merge(left,right)
	
arr = [6,5,4,2,1,3]
print(merge_sort(arr))