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) 

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)