CODEWITHSUNDEEP
pythonarrayssortingrecursionmergesort
Adrienne
Adrienne

Reputation: 2680

Why doesn't this python implementation of mergesort work?

When I input [8,7,6,5,4,3,2,1] the output is => [4, 3, 2, 1, 8, 7, 6, 5].

It seems like the only thing different from a working solution (comparing here) is that instead of a sorted list, I have a k variable that I am incrementing, and update arr[k] in place of sorted.

Why doesn't this work? And how does updating arr[k] work? It seems like you would be losing data by updating the original input array.

def mergesort(arr):
    if len(arr) == 1:
        return

    else:
        mid = len(arr)/2
        left = arr[0:mid]
        right = arr[mid:len(arr)]

        sorted = []
        i = 0
        j = 0
        mergesort(left)
        mergesort(right)

        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                sorted.append(left[i])
                i += 1
            else:
                sorted.append(right[j])
                j += 1

        while i < len(left):
            sorted.append(left[i])
            i += 1

        while j < len(right):
            sorted.append(right[j])
            j += 1

        return sorted

Upvotes: 1

Views: 292

Answers (1)

m7mdbadawy
m7mdbadawy

Reputation: 920

You should just assign to left and right variable as you function return the sorted list after sorting also in the base case you should return a list and use // for integer division check this code

def mergesort(arr):
    if len(arr) == 1:
        return arr

    else:
        mid = len(arr)//2
        left = arr[0:mid]
        right = arr[mid:len(arr)]

        sorted = []
        i = 0
        j = 0
        left = mergesort(left) #left is now sorted
        right = mergesort(right)

        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                sorted.append(left[i])
                i += 1
            else:
                sorted.append(right[j])
                j += 1

        while i < len(left):
            sorted.append(left[i])
            i += 1

        while j < len(right):
            sorted.append(right[j])
            j += 1

        return sorted

print (mergesort([8,7,6,5,4,3,2,1,3]))

Upvotes: 2

Related Questions