Merge Sort Algorithm in Python

Question 1

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

import unittestimport randomdef 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 seqclass 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()

Question 2

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

Question 3

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 mergedef 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

Question 4

Usingheapq.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 useheapq.merge, why not just usesorted?

Question 5

that is true; I also have a bunch of tips for his coding style though

Question 6

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

You could've just said:

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

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

Question 7

Just a couple of comments.

Your base case should beif len(seq) <= 1: return seq, notif len(seq) == 1: return seq.
If you're striving for efficiency, you shouldn't create so many intermediate sequences. Have a look atthis for a solution which uses only a single temporary array (it's C#, but the difference is just syntactic).

Question 8

Reducing nesting

It is easier to not useelse 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.

mikemaccana 1791 silver badge6 bronze badges · Answer 1 · 2014-11-25 18:26:03Z