The Half That Vanished
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.extend(right[j:])
return out
def merge_sort(a):
if len(a) <= 1: return a
mid = len(a) // 2
return merge(merge_sort(a[:mid]), merge_sort(a[mid:]))
merge_sort sometimes returns a list shorter than its input. What is the shortest input that triggers it?
Sign in to answer questions and track your progress
Sign In