Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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()
share|improve this question
add comment

2 Answers

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

share|improve this answer
1  
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.