# Merge Sort Algorithm in Python

Implementing basic sorting algorithms to learn them, and coding, better. Criticisms/ critiques welcome. Also possible optimizations.

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()

-

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? –  Gareth Rees Feb 5 at 21:48
that is true; I also have a bunch of tips for his coding style though –  ASKASK Feb 5 at 21:48
(1) Your base case should be if len(seq) <= 1: return seq, not if len(seq) == 1: return seq.