CODEWITHSUNDEEP
python-3.xalgorithmsortingmergesort
Somil Shah
Somil Shah

Reputation: 109

Why is my merge sort algorithm not working?

I am implementing the merge sort algorithm in Python. Previously, I have implemented the same algorithm in C, it works fine there, but when I implement in Python, it outputs an unsorted array.

I've already rechecked the algorithm and code, but to my knowledge the code seems to be correct.

I think the issue is related to the scope of variables in Python, but I don't have any clue for how to solve it.

from random import shuffle
# Function to merge the arrays
def merge(a,beg,mid,end):
    i = beg
    j = mid+1
    temp = []
    while(i<=mid and j<=end):
        if(a[i]<a[j]):
            temp.append(a[i])
            i += 1
        else:
            temp.append(a[j])
            j += 1
    if(i>mid):
        while(j<=end):
            temp.append(a[j])
            j += 1
    elif(j>end):
        while(i<=mid):
            temp.append(a[i])
            i += 1

    return temp



# Function to divide the arrays recursively
def merge_sort(a,beg,end):
    if(beg<end):
        mid = int((beg+end)/2)
        merge_sort(a,beg,mid)
        merge_sort(a,mid+1,end)
        a = merge(a,beg,mid,end)

    return a

a = [i for i in range(10)]
shuffle(a)
n = len(a)
a = merge_sort(a, 0, n-1)
print(a)

Upvotes: 2

Views: 309

Answers (2)

IcedLance
IcedLance

Reputation: 426

To make it work you need to change merge_sort declaration slightly:

def merge_sort(a,beg,end):
    if(beg<end):
        mid = int((beg+end)/2)
        merge_sort(a,beg,mid)
        merge_sort(a,mid+1,end)
        a[beg:end+1] = merge(a,beg,mid,end)  # < this line changed
    return a

Why:

temp is constructed to be no longer than end-beg+1, but a is the initial full array, if you managed to replace all of it, it'd get borked quick. Therefore we take a "slice" of a and replace values in that slice.

Why not:

Your a luckily was not getting replaced, because of Python's inner workings, that is a bit tricky to explain but I'll try. Every variable in Python is a reference. a is a reference to a list of variables a[i], which are in turn references to a constantant in memory. When you pass a to a function it makes a new local variable a that points to the same list of variables. That means when you reassign it as a=*** it only changes where a points. You can only pass changes outside either via "slices" or via return statement

Why "slices" work:

Slices are tricky. As I said a points to an array of other variables (basically a[i]), that in turn are references to a constant data in memory, and when you reassign a slice it goes trough the slice element by element and changes where those individual variables are pointing, but as a inside and outside are still pointing to same old elements the changes go through.

Hope it makes sense.

Upvotes: 1

user1196549
user1196549

Reputation:

You don't use the results of the recursive merges, so you essentially report the result of the merge of the two unsorted halves.

Upvotes: 0

Related Questions