Merge Sort Algorithm in Python

Question

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

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

Just a couple of comments.

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

Answer 5

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.