views:

682

answers:

2

I've implemented what I believe to be a merge sort algorithm in python. I've never programmed in Python before, so I used several resources with commands that seemed foreign to me, to gain a better understanding.

However, I've also never implemented merge sort in the first place, so I'm not sure if I've even implemented it correctly. Any guidance, tips, or corrections would be greatly appreciated.

Here is my merge method:

def merge(left, right):
    result = []
    i, j = 0, 0
    while(i < len(left) and j< len(right)):
     if(len(left[i]) <= len(right[j])): 
      print(i)
      result.append(left[i])
      i=i+1
     else:
      result.append(right[j])
      j=j+1

    result += left[i:]
    result += right[j:]
    return result

meanwhile, here is my mergesort method:

def mergesort(list):
    if len(list) < 2:
     return list
    else:
     middle = len(list) / 2
     left = mergesort(list[:middle])
     right = mergesort(list[middle:])
     return merge(left, right)

Thanks for any possible help! :)

+2  A: 

Don't name variables "list". That's the name of Python's array type, so using a variable by the same name is confusing.

When you return from a conditional, you don't need to sitck the rest of the function in an else block.

def mergesort(list):
    if len(list) < 2:
        return list
    middle = len(list) / 2
    left = mergesort(list[:middle])
    right = mergesort(list[middle:])
    return merge(left, right)

Overall, it looks reasonable.

Of course, for anything but an exercise, you should be using list.sort or sorted().

a = ["abc", "de", "f", "ghijkl"]
print sorted(a, lambda a,b: cmp(len(a), len(b)))
Glenn Maynard
thanks for that! i don't know which words are keywords for the language yet. I'm not sure what example would be better for learning the language, so i'm just going with it. thanks for your tips!
Chris
however, i have an issue with the method. it seems to be simply returning the list exactly how it's passed in. i am simply calling mergesort(originalArray) to sort it. This seems reasonable, correct?
Chris
My bad, I was calling this improperly.
Chris
list (and other builtin types) isn't actually a keyword; you *can* use the name if you want. It's just best to avoid it. If it was a keyword (eg. for, def), you'd get a compile error.
Glenn Maynard
Note if you just want to sort a list in-place, you can just use a.sort(...) instead of a = sorted(a, ...).
Glenn Maynard
+2  A: 

How about using the sorted() function? Like this:

def len_cmp(x, y):
    return len(x) - len(y)

my_strings = ["hello", "foo", "bar", "spam"]
print sorted(my_strings, len_cmp)
Evan Fosmark
wasn't aware of the sorted function, thanks :) where could i find documentation on how it is implemented?
Chris
You can find a decent explaination here: http://wiki.python.org/moin/HowTo/SortingIt's pretty handy. :)
Evan Fosmark