Merge sort is a classic divide and conquer algorithm: split the array in half, sort each half recursively and merge the two sorted halves in O(n). Its running time is O(n log n) in every case, it is stable, but it needs O(n) extra memory. For the idea of recursion trees see divide and conquer.
Merging two sorted lists
Look at the heads of both lists and move the smaller one to the result. When one list ends, append the remainder of the other: it is already sorted. This takes O(n + m). On a tie we take the element from the left list, which makes the merge stable.
def merge(left, right):
out = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i])
i += 1
else:
out.append(right[j])
j += 1
out += left[i:]
out += right[j:]
return out
print(merge([1, 4, 7], [2, 3, 9]))
print(merge([], [5]))
print(merge([(1, "a"), (2, "a")], [(1, "b"), (2, "b")]))[1, 2, 3, 4, 7, 9]
[5]
[(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')]Recursive merge sort
A list of 0 or 1 elements is already sorted. Otherwise split the list in half, sort the halves and merge them.
