Mergesort in Python, my first sorting algorithm, what went wrong?

Question

def mergesort(a):
    if len(a)<=1:
        return a

    else:
        mid=len(a)/2
        mergesort(a[:mid])
        mergesort(a[mid:])
        auxa=[]
        j=0
        k=mid
        while j<mid and k<len(a):
            if a[j]<a[k]:
                auxa.append(a[j])
                j+=1
            else:
                auxa.append(a[k])
                k+=1

        if j==mid:
            auxa.extend(a[k:])

        if k==len(a):
            auxa.extend(a[j:mid])

        a=auxa


        return a

testlist=[3,2,1]   
print mergesort(testlist)

the result I got is 2 1 3

any help is much appreciated, thanks!

do not ignore the returned value from internal mergesort() calls — jfs
– jfs, Commented Dec 10, 2013 at 0:13

santosh.ankr · Accepted Answer · 2013-12-10 00:48:52Z

4

Your function mergesort returns a new list, and does not modify the one you supplied it, as you seem to expect it to be doing. So when you call mergesort(a[:mid]) for example, what you get back is a new sorted version of those elements, while the original a[:mid] stays exactly the same.

EDIT: The issue here is the way python list slicing works. When you say a[:mid], python creates a 'copy' ( let's not worry about the exact type of copy ) of the original. Now when you modify this copy in a function, all you're doing is changing the references in it to point to new integers, not modifying the original in any way. Here's some code to flesh this out:

def change(a):
    a[1] = 0

a = [1, 2, 3]
change(a)
a
>> [1, 0, 3]

a = [1, 2, 3]
change(a[:2])
a
>> [1, 2, 3]

EDIT 2: Copying back the values done correctly (as suggested by (abamert) in the comments):

def mergesort(a):
  if len(a)<=1:
    return a

  else:
    mid=len(a)/2
    a = mergesort(a[:mid]) + mergesort(a[mid:])
    auxa=[]
    j=0
    k=mid
    while j<mid and k<len(a):
        if a[j]<a[k]:
            auxa.append(a[j])
            j+=1
        else:
            auxa.append(a[k])
            k+=1

    if j==mid:
        auxa.extend(a[k:])

    if k==len(a):
        auxa.extend(a[j:mid])


    return auxa

This are obviously better ways to do this with less copying involved, but I think this solution is slightly more relevant to the issue with the original code.

edited Dec 10, 2013 at 0:48

answered Dec 10, 2013 at 0:09

santosh.ankr

6714 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

abarnert Over a year ago

Good explanation, but I think you also want to provide the solution. Just do a[:mid] = mergesort(a[:mid]) if you want to change the first half in place. Or, probably better, use a = mergesort(a[:mid]) + mergesort(a[mid:]) to created a new sorted list out of the two sorted halves.

jfs Over a year ago

i don't see a[index] = value anywhere in the OP's code i.e., it doesn't matter whether a parts are passed as a copy or not, a is not changed anyway. local_a = whatever has no influence on outside world unless it is returned from the function. But OP ignores the returned value from mergesort() <-- this is the real issue.

santosh.ankr Over a year ago

I suppose it is a matter of interpretation. Your point of view is that OP intended to get the return value of his function and use it, but forgot. The fact that he has a return statement supports this. My point of view is that he expected the change to happen to the passed array. The fact that he attempts to do a = auxa supports this. Depending on which one you agree with more, the issue is either slice-copy or OP ignoring return value, arguing which is the "real" one does not make too much sense to me.

santosh.ankr Over a year ago

local_a = whatever .... I agree, of course. Point is it may not have been obvious to OP that it was indeed local a. But semantics, really.

Less Talk -- More Synthehol · Accepted Answer · 2013-12-10 17:27:39Z

3

Here's what I came up with:

from collections import deque

def mergesort(array):
    if len(array) <= 1: return array

    midpoint = len(array) / 2

    left_array = deque(mergesort(array[:midpoint]))
    right_array = deque(mergesort(array[midpoint:]))

    merged_array = deque([])

    while len(left_array) and len(right_array):
        if left_array[0] < right_array[0]:
            merged_array.append(left_array.popleft())
        else:
            merged_array.append(right_array.popleft())

    merged_array.extend(left_array)
    merged_array.extend(right_array)

    return merged_array

print mergesort([3, 2, 1])

edited Dec 10, 2013 at 17:27

answered Dec 10, 2013 at 0:17

Less Talk -- More Synthehol

464 bronze badges

1 Comment

jfs Over a year ago

pop(0) is O(n) for lists, it makes your algorithm quadratic instead of usual O(n*log n) for mergesort. You could try collections.deque() instead of the merged_array list. while left_array and right_array: works as is. After the first loop either left_array or right_array is empty. You could use merged_array.extend(left_array); merged_array.extend(right_array); instead of the last two loops. To support Python 3, you could use // (floor division).

Collectives™ on Stack Overflow

Mergesort in Python, my first sorting algorithm, what went wrong?

2 Answers 2

4 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related