A sort composed of breaking down an array into minimal sets (2, if remainder then 3), then sorting and popping the smallest number when joining.

Implementation

from random import randint
data = [randint(1, 100) for x in range(10)]

# utility functions
def swap(from_pos: int, to_pos: int, arr: list[int]) -> None:
	arr[from_pos], arr[to_pos] = arr[to_pos], arr[from_pos]

# recursive implementation
def merge_sort(arr: list[int]):
	if len(arr) > 3:
		first_part = arr[:len(arr) // 2]
		first_part_empty = first_part == []
		merge_sort(first_part)
		
		second_part = arr[len(arr) // 2:]
		second_part_empty = second_part == []
		merge_sort(second_part)
		
		arr.clear()
		
		while not first_part_empty or not second_part_empty:
			if not first_part_empty and not second_part_empty:
				arr.append(first_part.pop(0) if first_part[0] < second_part[0] else second_part.pop(0))
			elif not first_part_empty:
				arr.append(first_part.pop(0))
			else:
				arr.append(second_part.pop(0))
			first_part_empty = first_part == []
			second_part_empty = second_part == []
	else:
		match len(arr):
			case 2:
				if arr[0] > arr[1]:
					swap(0, 1, arr)
			case 3:
				if arr[0] > arr[1]:
					swap(0, 1, arr)
				if arr[1] > arr[2]:
					swap(1, 2, arr)
				if arr[0] > arr[1]:
					swap(0, 1, arr)

merge_sort(data)
print(data)

Advantages

• Fast on large datasets
• O(n log n) speed

Disadvantages

• Hard to program
• O(n) space
• Negligible speed benefits on small datasets