CODEWITHSUNDEEP
pythonalgorithmsortingmergemergesort
david nadal
david nadal

Reputation: 279

Why can't I implement merge sort this way

I understand mergesort works by divide and conquer, you keep halving until you reach a point where you can sort in constant time or the list is just one lement and then you merge the lists.

def mergesort(l):
    if len(l)<=1:
        return l
    l1 = l[0:len(l)//2+1]
    l2 = l[len(l)//2:]

    l1 = mergesort(l1)
    l2 = mergesort(l2)

    return merge(l1,l2)

I have a working merge implementation and I checked it works fine but the merge sort implementation does not work it just returns half of the elements of the list.

I see on the internet mergesort is implemented using l & r and m = (l + r)/2. What is wrong with my implementation? I am recursively subdividing the list and merging too.

Upvotes: 1

Views: 319

Answers (2)

Andrew J. McGehee
Andrew J. McGehee

Reputation: 64

The code you have listed doesn't appear to do any sorting. I can't know for certain because you haven't listed the merge() function's code, but the only thing that the above function will do is recursively divide the list into halves. Here is a working implementation of a merge sort:

def mergeSort(L):

    # lists with only one value already sorted
    if len(L) > 1:
        # determine halves of list
        mid = len(L) // 2
        left = L[:mid]
        right = L[mid:]

        # recursive function calls
        mergeSort(left)
        mergeSort(right)

        # keeps track of current index in left half
        i = 0
        # keeps track of current index in right half
        j = 0
        # keeps track of current index in new merged list
        k = 0

        while i < len(left) and j < len(right):
            # lower values appended to merged list first
            if left[i] < right[j]:
                L[k] = left[i]
                i += 1
            else:
                L[k] = right[j]
                j += 1
            k += 1

        # catch remaining values in left and right
        while i < len(left):
            L[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            L[k] = right[j]
            j += 1
            k += 1
    return L

Your function makes no comparisons of values in the original list. Also, when you are splitting the list into halves in:

l1 = l[0:len(l)//2 + 1]

the '+ 1' is unnecessary (and can actually cause incorrect solutions). You can simply use:

l1 = l[:len(l)//2]

If the length is even (i.e 12) it will divide the two halves from [0:6] and [6:12]. If it is odd it will still automatically divide correctly (i.e. length = 13 would be [0:6] and [6:13]. I hope this helps!

Upvotes: 0

mehrdadep
mehrdadep

Reputation: 1019

the problem is the +1 in your code, here:

l1 = l[0:len(l)//2]
l2 = l[len(l)//2:]

replace this with your code and you're be fine

Upvotes: 3

Related Questions