Python Merge Sort Algorithm

Question

Hi I am attempting to make a Merge Sort algorithm for fun, and do not want to just copy code off the internet. Which is why I have not referred to another person's Stack Overflow thread. So unless the thread has the same issue, please do not direct me towards that. I am using 2 functions, merge and merge sort. Merge sort is recursive, I intend for it to split a list in half, and then sort each half. The merge algorithm should then take the two sorted lists and return a new list, which is just the two lists combined and sorted. Eventually the code should return a fully sorted list. Below is my code, and if you run it you will see that I am getting an empty list returned, which makes no sense to me. Any help would be greatly appreciated. Thanks :)

def merge(left, right):
    resultList = []
    leastRight = 0
    leastLeft = 0
    if len(left) >= len(right):
        for i in range(len(left)-1):
            counter = 0
            for j in range(len(right)-1):
                counter += 1
                if right[counter % (len(right)-1)] <= right[j]:
                    leastRight = right[counter % (len(right)-1)]
                    print("leastRight if",leastRight)
                else:
                    leastRight = right[j]
                    print("leastRight else", leastRight)
                right.remove(leastRight)
            if left[i] <= leastRight:
                resultList.append(left[i])
            else:
                resultList.append(leastRight)
    else:
        for i in range(len(right)-1):
            counter = 0
            for j in range(len(left)-1):
                counter += 1
                if left[counter % (len(left)-1)] <= left[j]:
                    leastLeft = left[counter%(len(left)-1)]
                    print("leastLeft if", leastLeft)
                else:
                    leastLeft = left[j]
                    print("leastLeft else", leastLeft)
                left.remove(leastLeft)
            if right[i] <= leastLeft:
                resultList.append(right[i])
            else:
                resultList.append(leastLeft)
return (resultList)

def mergeSort(alist):

    print("alist", alist)
    if len(alist) > 2:
        middleIndex = len(alist) // 2
        sortedLeft = mergeSort(alist[:middleIndex])
        print("left", sortedLeft)
        sortedRight = mergeSort(alist[middleIndex:])
        print("right", sortedRight)
        result = merge(sortedLeft, sortedRight)
        print("result", result)
    else:
        result = alist
    return (result)

print("mergesort", mergeSort([6, 0, 2, 8, 9, 1]))

… where it would provoke advice like rather than duplicate code with roles of variables swapped, swap their values: if len(left) >= len(right): left, right = right, left. — greybeard
– greybeard, Commented Apr 1, 2021 at 7:47

MBo · Accepted Answer · 2021-04-01 09:54:16Z

Sorry, but approach of your merge function is not usable at all. Principle of choosing the smallest element is too tangled here and causes errors (I just saw it cannot merge [6] and [0,2]). Have you read classical description of merging?

In mergesort (we cannot omit treatment of length 2 lists):

if len(alist)   >=    2:

Quick-made working implementation of merge routine.

def merge(left, right):
    resultlist = []
    llen = len(left)
    rlen = len(right)
    il = 0
    ir = 0
    while il < llen and ir < rlen:  #while both list are not exhausted
        if left[il] <= right[ir]:    #choose the smallest current item
            resultlist.append(left[il])
            il += 1
        else:
            resultlist.append(right[ir])
            ir += 1
       #now treat the rest tail
    while il < llen:  
        resultlist.append(left[il])
        il += 1
    while ir < rlen:
        resultlist.append(right[ir])
        ir += 1
    return resultlist

result

>>> mergesort [0, 1, 2, 6, 8, 9]

Note it would be wise to make resultlist of known length for speed.

def merge(left, right):
    llen = len(left)
    rlen = len(right)
    resultlist = [0]*(llen+rlen) # we know data type and full length
    il = 0
    ir = 0
    k = 0
    while il < llen and ir < rlen:
        if left[il] <= right[ir]:
            resultlist[k] = left[il]
            il += 1
        else:
            resultlist[k] = right[ir]
            ir += 1
        k += 1
    while il < llen:
        resultlist[k] = left[il]
        il += 1
        k += 1
    while ir < rlen:
        resultlist[k] = right[ir]
        ir += 1
        k += 1
    return resultlist

Collectives™ on Stack Overflow

Python Merge Sort Algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related