This simple change is about 3x as fast. I think it is relevant because the same should be done in the original c code. 2x comes from the list swap, the rest com

This simple change is about 3x as fast. I think it is relevant because the same should be done in the original c code. 2x comes from the list swap, the rest comes from the use of N in the while conditional. def merge2(l1, l2): if len(l1) == 0: return [x for x in l2] if len(l2) == 0: return [x for x in l1] # ensure l1 is exhausted first to minimize # comparisons if l1[-1] > l2[-1]: l1, l2 = l2, l1 sorted_list = [] i = 0 j = 0 N = len(l1) while i < N: if l1[i] <= l2[j]: sorted_list.append(l1[i]) i += 1 else: sorted_list.append(l2[j]) j += 1 sorted_list.extend(l2[j:]) return sorted_list