def merge_sort(a, left=0, right=None):
	if right is None:
		right = len(a)
 
	if right - left > 1:
		middle = (left + right) // 2
		merge_sort(a, left, middle)
		merge_sort(a, middle, right)
		merge(a, left, middle, right)


def merge(a, left, middle, right):
	first = a[left:middle]
	second = a[middle:right]
 
	i, j = 0, 0
	for k in range(left, right):
		if i < len(first) and (j == len(second) or first[i] <= second[j]):
			a[k] = first[i]
			i += 1
		else:
			a[k] = second[j]
			j += 1