Indentation

I get a syntax error on my version of Python due to the indentationof 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. Perhapsyour version of Python is more forgiving, or perhaps there was aproblem when you pasted the code into the question.

Naming

sort is the name of a built-in list method. It would be better to renameyour 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 beitems, or something more specificto this application.

The same applies to the arguments of themerge function

left,right

Since they are arrays:

lefts, rights

DRY

In thesort 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 thisfor loop:

for i in l_rest:    out.append(i)

You could simply use theextend 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

ThePEP 8 style guide recommendsadding docstrings for functions. The docsrting should summarizewhat the function does, and it should describe the input types andreturn type. It should mention that thesort function is recursive.

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 + rightdef sort(lst):    if len(lst) == 1:        return lst    left = sort(lst[:len(lst)//2])    right = sort(lst[len(lst)//2:])    return merge(left,right)

• \$\begingroup\$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.\$\endgroup\$

  Toby Speight

  – Toby Speight

  2025-03-13 10:53:20 +00:00

  CommentedMar 13 at 10:53

• python
• python-3.x
• sorting
• mergesort