Medium Divide & Merge Sorting
In plain English: Sort a list by splitting it in half, sorting each half, and merging them back together.
Divide and conquer: splitting halves the problem, merging combines sorted halves in linear time — guaranteed O(n log n).
Prompt
Sort an array using merge sort.
Try to write it from scratch before scrolling down.
Solution
def merge_sort(a):
if len(a) <= 1:
return a
m = len(a) // 2 # divide at midpoint
L = merge_sort(a[:m])
R = merge_sort(a[m:])
res, i, j = [], 0, 0
while i < len(L) and j < len(R):
if L[i] <= R[j]:
res.append(L[i]); i += 1
else:
res.append(R[j]); j += 1
res.extend(L[i:])
res.extend(R[j:])
return res
# Test: merge_sort([38,27,43,3,9,82,10]) == [3,9,10,27,38,43,82]