10 ms·
Well the version I'm saying is essentially the same as the pop version you have so I don't think it's too complicated. You would just do something like this ins
by CogitoCogito 5y ago
Well the version I'm saying is essentially the same as the pop version you have so I don't think it's too complicated. You would just do something like this instead:
def merge_sorted_lists(l1, l2):
sorted_list = []
i = 0
j = 0
while i < len(l1) or j < len(l2):
if i == len(l1):
sorted_list.append(l2[j])
j += 1
continue
if j == len(l2):
sorted_list.append(l1[i])
i += 1
continue
if l1[i] < l2[j]:
sorted_list.append(l1[i])
i += 1
else:
sorted_list.append(l2[j])
j += 1
return sorted_list
I haven't tested that (you probably should before using it), but it looks mostly right and is essentially the same algorithm as yours.
- RogerL 5y agoThis 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