def insertion_sort(arr):
	for i in range(1, len(arr)):
		key = arr[i]
		j = i - 1

		while j >= 0 and arr[j] > key:
			arr[j+1] = arr[j]
			j -= 1

		arr[j+1] = key

	return arr

def shell_sort(arr):
	n = len(arr)
	gap = n // 2

	while gap > 0:
		for i in range(gap, n):
			temp = arr[i]
			j = i

			while j >= gap and arr[j-gap] > temp:
				arr[j] = arr[j-gap]
				j -= gap

			arr[j] = temp
		gap //= 2

	return arr

def bubble_sort(arr):
	n = len(arr)

	for i in range(n):
		swapped = False

		for j in range(n-i-1):
			if arr[j] > arr[j+1]:
				arr[j], arr[j+1] = arr[j+1], arr[j]
				swapped = True

		if not swapped:
			break

	return arr

def bubble_sort(arr):
	n = len(arr)
	last_swap = n - 1

	while last_swap > 0:
		curr_swap = 0

		for i in range(last_swap):
			if arr[i] > arr[i+1]:
				arr[i], arr[i+1] = arr[i+1], arr[i]
				curr_swap = i

		last_swap = curr_swap

	return arr

def quick_sort(arr):
	if len(arr) <= 1:
		return arr

	pivot = arr[0]
	left = [x for x in arr[1:] if x <= pivot]
	right = [x for x in arr[1:] if x > pivot]

	return quick_sort(left) + [pivot] + quick_sort(right)

def partition(arr, low: int, high: int) -> int:
	pivot = arr[high]
	i = low - 1

	for j in range(low, high):
		if arr[j] <= pivot:
			i += 1
			arr[i], arr[j] = arr[j], arr[i]

	arr[i + 1], arr[high] = arr[high], arr[i + 1]
	return i + 1

def quick_sort(arr, low, high):
	if low >= high:
		return
	pivot_idx = partition(arr, low, high)
	quick_sort(arr, low, pivot_index - 1)
	quick_sort(arr, pivot_index + 1, high)

def selection_sort(arr):
	n = len(arr)

	for i in range(n):
		min_index = i
		for j in range(i+1, n):
			if arr[j] < arr[min_index]:
				min_index = j

		arr[i], arr[min_index] = arr[min_index], arr[i]

	return arr

def heapify(arr, n, i):
	largest = i

	if (left := get_left(i)) < n and arr[left] > arr[largest]:
		largest = left
	if (right := get_right(i)) < n and arr[right] > arr[largest]:
		largest = right

	if largest == i:
		return

	arr[i], arr[largest] = arr[largest], arr[i]
	heapify(arr, n, largest)

def heap_sort(arr):
	n = len(arr)

	for i in range(n//2-1, -1, -1):
		heapify(arr, n, i)

	for i in range(n-1, 0, -1):
		arr[0], arr[i] = arr[i], arr[0]
		heapify(arr, i, 0)

	return arr

def merge(left, right):
	result = []
	i = j = 0

	while i < len(left) and j < len(right):
		if (l := left[i]) <= (r := right[j]):
			result.append(l)
			i += 1
		else:
			result.append(r)
			j += 1

	result.extend(left[i:])
	result.extend(right[j:])

	return result

def merge_sort(arr):
	if (n := len(arr)) < 2:
		return arr

	mid = n // 2
	left = arr[:mid]
	right = arr[mid:]

	left = merge_sort(left)
	right = merge_sort(right)

	return merge(left, right)