Merge Sort Using Python

Question

I didn't get the sorted list, instead only one value.

def merge1(left,right):
    print("left" , left , "right" , right)
    def loop(left,right,ss):
        print("left" , left , "right" , right)
        if not (left ==[] or right ==[]):
            if left[0] <= right[0]:
                ss.append(left[0]) 
                return loop(left[1:],right, ss)
            else:
                ss.append(right[0])
                return loop(left,right[1:], ss)
            print("hello")
        else:
            return ss
    return loop(left,right,[])


def msort(s):
    if len(s)>1:
        mid = len(s) // 2
        return merge1(msort(s[:mid]),msort(s[mid:]))
    else:
        return s

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

I suggest you compare to this implementation: interactivepython.org/courselib/static/pythonds/SortSearch/… — robert
– robert, Commented Oct 8, 2015 at 18:16
Try using a simpler example. For example, what should merge1([1], [2]) return, and what does it actually return? What about merge1([1], [])? — Kevin
– Kevin, Commented Oct 8, 2015 at 18:17

ziddarth · Accepted Answer · 2015-10-08 18:37:38Z

1

You are not addressing the case where either one of the left or right array is exhausted. You will have to copy the remaining values from the non-empty array to the merged array:

def merge1(left,right):
    print("left" , left , "right" , right)
    def loop(left,right,ss):
        print("left" , left , "right" , right)
        if left and right:
            if left[0] <= right[0]:
                ss.append(left[0]) 
                return loop(left[1:],right, ss)
            else:
                ss.append(right[0])
                return loop(left,right[1:], ss)
        # either one of left or right is empty so you need to copy the remaining
        # values into merged array
        else:
            if left:
                for i in left:
                    ss.append(i)
            if right:
                for i in right:
                    ss.append(i)
            print ss
            return ss
    return loop(left,right,[])


def msort(s):
    if len(s)>1:
        mid = len(s) / 2
        return merge1(msort(s[:mid]),msort(s[mid:]))
    else:
        return s

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

answered Oct 8, 2015 at 18:37

ziddarth

1,9361 gold badge16 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

J.Doe Over a year ago

thanks, meaning that if left or right becomes exhausted, it will still be in the merged array?

ziddarth Over a year ago

yes, say you are merging two lists where one is empty([1, 2, 3], []) you need to return [1, 2, 3] as the merged array, in your original code this was not implemented.

Collectives™ on Stack Overflow

Merge Sort Using Python

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related