# Merge Sort Cleanup

I am re-learning my fundamental algorithms, and have been told my Python is overly verbose.
Can you take a look at my merge sort algorithm and let me know how you would clean it up and make it more pythonic, if applicable?

def merge(left,right):
out = []
l_rest = []
i = left
while i is not None:
if right:
if i < right:
out.append(i)
left.remove(i)
else:
out.append(right)
right.remove(right)
else:
out.append(i)
left.remove(i)

if len(left) > 0:
i = left
else:
i = None
for i in l_rest:
out.append(i)
for i in right:
out.append(i)
return out

def sort(lst):
if len(lst) == 1:
return lst

left = sort(lst[:len(lst)//2])
right = sort(lst[len(lst)//2:])
return merge(left,right)

• Your code seems to have a bug: it doesn't include the pivot in the result. – Solomon Ucko Apr 4 '18 at 16:18
• @SolomonUcko Thanks, not sure I follow, but I will debug tonight. – Chris Apr 4 '18 at 16:49
• Sorry, at first I thought it was quicksort. What I meant was that, for example, if I sort a list of the numbers 0-99, repeated 100 times, then shuffled, the 0s are missing. – Solomon Ucko Apr 4 '18 at 17:01
• why not just out += l_rest + right instead of for i in l_rest: out.append(i); for i in right: out.append(i) – Yulia V Apr 4 '18 at 18:21
• @SolomonUcko fixed, that was nasty. Thanks. I chose to fix that and not fix YuliaV's suggestion inline... Not sure the best practice for implementing incremental improvements, but I like their idea. – Chris Apr 5 '18 at 5:01

Starting a wiki with the suggested edits in the comments so far.

def merge(left,right):
out = []
i = left
while i is not None:
if right and i < right:
out.append(i)
left.remove(i)
else:
out.append(right)
right.remove(right)

if len(left) > 0:
i = left
else:
i = None

return out + left + right

def sort(lst):
if len(lst) == 1:
return lst

left = sort(lst[:len(lst)//2])
right = sort(lst[len(lst)//2:])
return merge(left,right)