CODEWITHSUNDEEP
python-3.xsortingmergesort
user14354509
user14354509

Reputation: 47

Can someone help me to figure out what's wrong in my implementation of merge sort?

My implementation:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

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

    merge_sort(left)
    merge_sort(right)

    return merge(left, right)

def merge(left, right):
    leftI = rightI = 0
    merged = []
    
    while (leftI < len(left) and rightI < len(right)):
        if left[leftI] < right[rightI]:
            merged.append(left[leftI])
            leftI += 1
        else:
            merged.append(right[rightI])
            rightI += 1
    
    merged.extend(left[leftI:])
    merged.extend(right[rightI:])
    
    return merged

if __name__ == '__main__':
    arr = [1,2,5,5,9,22,6,3,6,8,1,43,5]
    print(merge_sort(arr))

For some reason I am obtaining:

[1, 2, 5, 5, 6, 3, 6, 8, 1, 9, 22, 43, 5]

Working Implementation (Got from a friend):

def merge_sort(list):
    list_length = len(list)

    if list_length == 1:
        return list

    mid_point = list_length // 2

    left_partition = merge_sort(list[:mid_point])
    right_partition = merge_sort(list[mid_point:])

    return merge(left_partition, right_partition)


def merge(left, right):
    output = []
    i = j = 0

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

    return output

if __name__ == '__main__':
    arr = [1,2,5,5,9,22,6,3,6,8,1,43,5]
    print(merge_sort(arr))

This code yeilds:

[1, 1, 2, 3, 5, 5, 5, 6, 6, 8, 9, 22, 43]

I just can't figure out what's wrong. It'd be a great help if someone could take a few moments to help me out :)

Upvotes: 1

Views: 54

Answers (1)

Log1k
Log1k

Reputation: 95

In your merge_sort function, you do not change the values of left and right depending on what merge_sort returns. You have :

merge_sort(left)
merge_sort(right)

Where it should be :

left = merge_sort(left)
right = merge_sort(right)

Upvotes: 2

Related Questions