def selection_sort(lst):
	n = len(lst)
	for i in range(n):
		# find the index of the smallest remaining value
		min_index = i
		for j in range(i+1, n):
			if lst[j] < lst[min_index]:
				min_index = j
		
		# swap the smallest value into place
		tmp = lst[i]
		lst[i] = lst[min_index]
		lst[min_index] = tmp

def insertion_sort(lst):
	n = len(lst)
	for i in range(n):
		j = i
		while j > 0 and lst[j-1] > lst[j]:
			# swap the current value one space left
			tmp = lst[j]
			lst[j] = lst[j-1]
			lst[j-1] = tmp
			j -= 1

def merge_sort(lst):
	# if the list is this short, no sorting is necessary
	if len(lst) <= 1:
		# return a copy, out-of-place
		return list(lst)
	
	# half the length, rounded down
	m = len(lst) // 2
	
	# list slicing
	A = lst[:m]
	B = lst[m:]
	
	# sort both halves recursively
	A = merge_sort(A)
	B = merge_sort(B)
	
	return linear_merge(A, B)

def linear_merge(A, B):
	# merge two sorted lists
	output = []
	i, j = 0, 0
	
	while i + j < len(A) + len(B):
		if i < len(A) and (j == len(B) or A[i] <= B[j]):
			output.append(A[i])
			i += 1
		else:
			output.append(B[j])
			j += 1
	
	return output