Re:Beating TimSort at Merging
by CogitoCogito on Tuesday July 13, 2021 @02:40PM
(#27824545)
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
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
Maybe I'll do a follow-up. Thanks for reading the article. I suspect you know way more about C extensions in Python than I do. I saw you have a talk on this topic.
I think you are totally right that pop is not the way to go, but using an offset to track the head, like the C example does. I actually put that in a footnote, because I was considering testing my python version but the SO answer mentioned pop being expensive.
I think the simple version is still great as psuedo-code for communicating a solution though and hopefully it makes the c code a bit easier to follow once you've seen the python version.