Python merge sort
Merge sort divides a sequence until each part has at most one item, then combines sorted parts. Two indices track the next unconsumed value in each half.
Python
def merge_sort(values):
if len(values) <= 1:
return values.copy()
middle = len(values) // 2
left = merge_sort(values[:middle])
right = merge_sort(values[middle:])
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
return merged + left[i:] + right[j:]
print(merge_sort([4, 1, 3, 2]))
assert merge_sort([]) == []
assert merge_sort([2, 1, 2]) == [1, 2, 2]