# Merge Sort Algorithm in Python

I'm implementing basic sorting algorithms to learn them, and coding, better. Criticisms and possible optimizations welcome.

import unittest
import random

def merge_sort(seq):
"""Accepts a mutable sequence. Utilizes merge_sort to sort in place, return
a sorted sequence"""
if len(seq) == 1:
return seq
else:
#recursion: break sequence down into chunks of 1
mid = len(seq)/2
left = merge_sort(seq[:mid])
right = merge_sort(seq[mid:])

i, j, k = 0, 0, 0 #i= left counter, j= right counter, k= master counter

#run until left or right is out
while i < len(left) and j < len(right):
#if current left val is < current right val; assign to master list
if left[i] < right[j]:
seq[k] = left[i]
i += 1; k += 1
#else assign right to master
else:
seq[k] = right[j]
j += 1; k += 1

#handle remaining items in remaining list
remaining = left if i < j else right
r = i if remaining == left else j

while r < len(remaining):
seq[k] = remaining[r]
r += 1; k += 1

return seq

class test_mergesort(unittest.TestCase):
def test_mergesort(self):
test = [random.randrange(0, 10000) for _ in range(2000)]
self.assertEqual(merge_sort(test), sorted(test))

if __name__ == '__main__':
unittest.main()


You currently have:

i, j, k = 0, 0, 0 #i= left counter, j= right counter, k= master counter


Don't write minified code. Use variable names.

left_counter, right_counter, master_counter = 0, 0, 0


if you are looking for places to improve your code, i noticed that in this:

    while i < len(left) and j < len(right):
#if current left val is < current right val; assign to master list
if left[i] < right[j]:
seq[k] = left[i]
i += 1; k += 1
#else assign right to master
else:
seq[k] = right[j]
j += 1; k += 1


you have k += 1 in both scenarios since it always occurs but you could also just put it outside of the if statement:

    while i < len(left) and j < len(right):
#if current left val is < current right val; assign to master list
if left[i] < right[j]:
seq[k] = left[i]
i += 1;
#else assign right to master
else:
seq[k] = right[j]
j += 1;
k += 1


It just generally looks nicer and makes more sense

Also, one more piece of criticism, you handle the remaining items interestingly, but it is a bit confusing the way you try to make it work for both left and right when it could easily just be done individually which is a lot more readable and less confusing.

you do this:

    #handle remaining items in remaining list
remaining = left if i < j else right
r = i if remaining == left else j

while r < len(remaining):
seq[k] = remaining[r]
r += 1; k += 1


whereas I would recommend something like this:

    #handle remaining items in remaining list

while i < len(left):
seq[k] = left[i]
i += 1; k+= 1;

while j < len(right):
seq[k] = right[j]
j += 1; k+= 1;


The clever part about this is that already either the left or right array is done, so at most only one of the while loops are called so we do not have to worry aobut them both being called

as pointed out below, this might not be in the spirit of the activity, but if you are using python 2.6+, there is already a merge function built in, and it can be achieved in a much smaller amount of code:

from heapq import merge

def merge_sort(m):
if len(m) <= 1:
return m

middle = len(m) / 2
left = m[:middle]
right = m[middle:]

left = merge_sort(left)
right = merge_sort(right)
return list(merge(left, right))


sidenote: even if you do not want to use externally defined methods, the above example is actually a very good example of very nice and readable code, and so what would be best in terms of clean coding would be to do that and build your own merge function from what you have written so far

• Using heapq.merge seems like it would be contrary to the spirit of the OP's exercise (that is, learning how merge sort works)! I mean, if you're going to use heapq.merge, why not just use sorted? Feb 5, 2014 at 21:48
• that is true; I also have a bunch of tips for his coding style though Feb 5, 2014 at 21:48

The way you handle the remaining items is confusing as ASKASK pointed out.

You could've just said:

#handle remaining items in remaining list
seq[k:] = left[i:] + right[j:]


Either left[i:] or right[j:] will be empty, so adding them will give you the remaining list.

1. Your base case should be if len(seq) <= 1: return seq, not if len(seq) == 1: return seq.

2. If you're striving for efficiency, you shouldn't create so many intermediate sequences. Have a look at this for a solution which uses only a single temporary array (it's C#, but the difference is just syntactic).

Reducing nesting

It is easier to not use else in a recursive function after the base case. If the base case condition is verified, then the function ends and the rest of the function is not run anyway.

def merge_sort(seq):
if len(seq) <= 1: # Credit to Rafe for the base-case
return seq
mid = ...
...


Nesting means complexity, reducing it is desirable.