Why won't my merge sort will not work?

[deanhystad]

No. Break only breaks you out of the innermost loop containing the break. Your merge logic is wrong. The problem occurs when you take an item from the right you end up discarding the item from the left. This is easy to see if you isolate the merge and add some print statements:

def merge(l, r):
    nu = []
    for x in l:
        print('x', x)
        if len(r)==0:
            nu.append(x)
        elif x<r[0]:
            nu.append(x)
        else:
            while x>=r[0]:
                numss    = r.pop(0)
                nu.append(numss)
                if len(r)==0: break
        print(nu)
           
    if len(r)!=0: #if the r list is left, attach
        for x in r:
            nu.append(x)
    return nu

merge([1, 3, 7], [2, 4, 5])

Output:
x 1
[1]
x 3
[1, 2]
x 7
[1, 2, 4, 5]

Notice that for x == 3 and x == 7 the x is not appended to the merged list.

Without the print statements it is difficult to see the problem because the merge logic is so convoluted. The problem is that you "consume" am item from the left every time through the for loop, but when the next number comes from the right there you discard the left number. It is lost. You could change your logic to catch this, but if you don't understand your own code it is time for redesign, not debugging. The merge is very simple:

If left[0] < right[0]
    merged.append(left.pop(0))
else
    merged.append(right.pop(0))

If you cannot see this in you code it means your code is wrong. Granted you need to loop and add a little protection to prevent indexing an empty list. If done well this adds little code.

!!!!! SPOILER ALERT !!!!! SPOILER ALERT !!!!! SPOILER ALERT !!!!! SPOILER ALERT !!!!!

    result = []
    while left and right:
        if left[0] < right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    return result + left + right

The primary logic is still clearly visible

If you want to use a for loop you can do that too. I don't think the intention is as clear, but this code works.

def merge_sort(numbers):
    if len(numbers)==1:
        return numbers

    mid = len(numbers) // 2
    left = merge_sort(numbers[:mid])
    right = merge_sort(numbers[mid:])

    merged = []
    for number in left:
        while right and right[0] < number:
            merged.append(right.pop(0))
        merged.append(number)  #<- This is the part you were missing
    return merged + right

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

For each number in left, merge all right values less than that number, then merge the left number