CODEWITHSUNDEEP
pythonmergesort
Lookout
Lookout

Reputation: 241

Python-Merge sort difficulties

I attempted to implement a merge sort, here is my code: 

def mergeSort(array):
    result=[]
    n=len(array)
    if n==1:
        result=array
    else:
        a=round(n/2)
        first=mergeSort(array[0:a])
        second=mergeSort(array[a:n])

        for i in range(len(first)):
            for j in range(len(second)):
                if first[i]<second[j]:
                    result.append(first[i])
                    i=i+1
                else:
                    result.append(second[j])
                    j=j+1
    return result

a=[5,4,1,8,7,6,2,3]
b=mergeSort(a)
print(b)

Unfortunately, the result turns out to be [1]. What is wrong with my function?

Upvotes: 1

Views: 188

Answers (1)

buydadip
buydadip

Reputation: 9417

A number of things...

Firstly, this is a recursive function, meaning you cannot create a list within the function, as you did here:

result=[]

This will simply reset your list after every recursive call, skewing your results. The easiest thing to do is to alter the list that is passed as a parameter to merge sort.

Your next problem is that you have a for loop within a for loop. This will not work because while the first for loop iterates over first, the second for loop will iterate over second for every increment of i, which is not what you want. What you need is to compare both first and second and extract the minimum value, and then the next minimum value, and so on until you get a sorted list. So your for loops need to be changed to the following:

while i < len(first) and j < len(second):

Which leads me to final problem in your code. The while loop will exit after one of the conditions are met, meaning either i or j (one or the other) will not have reached len(first) or len(second). In other words, there will be one value in either first or second that is unaccounted for. You need to add this unaccounted value to your sorted list, meaning you must implement this final excerpt at the end of your function:

remaining = first if i < j else second
r = i if remaining == first else j

while r < len(remaining):
    array[k] = remaining[r]
    r = r + 1 
    k = k + 1

Here r represents the index value where the previous while loop broke off. The while loop will then iterate through the rest of the remaining values; adding them to the end of your sorted list.

You merge sort should now look as follows:

def mergeSort(array):
    if len(array)==1:
        return array
    else:
        a=round(len(array)/2)
        first=mergeSort(array[:a])
        second=mergeSort(array[a:])
        i = 0
        j = 0
        k = 0
        while i < len(first) and j < len(second):
            if first[i]<second[j]:
                array[k] = first[i]
                i=i+1
                k=k+1
            else:
                array[k] = second[j]
                j=j+1
                k=k+1

        remaining = first if i < j else second
        r = i if remaining == first else j

        while r < len(remaining):
            array[k] = remaining[r]
            r += 1; k += 1

    return array

I tried to not alter your code as much as possible in order to make it easier for you to understand. However, if your difficulty in understanding what I did persists, try de-bugging your merge sort using multiple print statements so that you can follow the function's progress and see where it goes wrong.

Upvotes: 4

Related Questions