Merge Sort algorithm in Python

Question

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[0]
 while i is not None:
 if right:
 if i < right[0]:
 out.append(i)
 left.remove(i)
 else:
 out.append(right[0])
 right.remove(right[0])
 else:
 out.append(i)
 left.remove(i)
 
 if len(left) > 0:
 i = left[0]
 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)

• Solomon Ucko: Your code seems to have a bug: it doesn't include the pivot in the result.
• Chris: @SolomonUcko Thanks, not sure I follow, but I will debug tonight.
• Solomon Ucko: 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.
• Yulia V: why not just out += l_rest + right instead of for i in l_rest: out.append(i); for i in right: out.append(i)
• Chris: @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.

Answer 1

Indentation

I get a syntax error on my version of Python due to the indentation of these lines:

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

I had to move them one space to the left to fix the error. Perhaps your version of Python is more forgiving, or perhaps there was a problem when you pasted the code into the question.

Naming

sort is the name of a built-in list method. It would be better to rename your function:

def sort(lst):

to something like:

def merge_sort(lst):

It is common to use a plural noun for an array variable name. For example, lst could be items, or something more specific to this application.

The same applies to the arguments of the merge function

left,right

Since they are arrays:

lefts, rights

DRY

In the sort function, this expression is repeated a few times:

len(lst)

You could set that to a variable:

number = len(lst)

The code would be a little simpler and perhaps a little more efficient.

Simpler

For this line:

if len(left) > 0:

there is no need for the comparison. This is simpler:

if len(left):

There is no need for this for loop:

for i in l_rest:
 out.append(i)

You could simply use the extend list method:

out.extend(l_rest)

The same is true for this loop:

for i in right:

Or, as seen in the previous answer, + can also be used.

Documentation

The PEP 8 style guide recommends adding docstrings for functions. The docsrting should summarize what the function does, and it should describe the input types and return type. It should mention that the sort function is recursive.

Answer 2

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

def merge(left,right):
 out = []
 i = left[0]
 while i is not None:
 if right and i < right[0]:
 out.append(i)
 left.remove(i)
 else:
 out.append(right[0])
 right.remove(right[0])
 if len(left) > 0:
 i = left[0]
 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)

• Toby Speight: Thanks for posting this code. It's a good idea to summarise which changes you made, and why - a self-answer ought to review the code, just like any other answer.