Merge Sort

merge_sort.py

def merge_sort(array):
	if len(array) >= 2:
		mid = len(array) // 2
		left = merge_sort(array[:mid])
		right = merge_sort(array[mid:])
		return merge(left, right)
	else:
		return array

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