Why won't my merge sort will not work?

[ggg]

I am practicing algorithms.
I don't understand why the below code is not working.
It is suppose to be merge sort.
Also I am confused on how to best debug this issue myself?

def ms(ls):
  if len(ls)==1: #base case
    return ls
  else:
    mid = len(ls)//2
    l = ms(ls[:mid])
    r = ms(ls[mid:])
    nu=[] #return list

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

[bowlofred]

Imagine sorting [2, 1].

When you get to line 17, you'll pop the 1 off of r and put it into nu.

Since r is now empty, you'll then hop down to line 22, so the l list with 2 inside is abandoned and [1] is returned. Nothing checks at that point if elements remain in l

[ggg]

Imagine sorting [2, 1].

When you get to line 17, you'll pop the 1 off of r and put it into nu.

Since r is now empty, you'll then hop down to line 22, so the l list with 2 inside is abandoned and [1] is returned. Nothing checks at that point if elements remain in l

Awww, wait so you are saying that break doesn't just break the while, but also the for loop?

[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

[deanhystad]

Two other nitpicks.

There is no reason for the else: If len(ls) == 1 you will never get past the "return ls". There is no reason for the protection provided by the else, and no reason to lose the indent space.

def ms(ls):
  if len(ls)==1: #base case
    return ls
  else:
    mid = len(ls)//2
    l = ms(ls[:mid])
    r = ms(ls[mid:])
    nu=[] #return list

Indent should be 4, not 2. You code would be easier to read if the blocks were easier to see.

Never use lower case L or upper case O as variable names. It is too easy to mistake this as 1 or 0.

Use better function and variable names. This should clearly be called mergesort or merge_stort. The left and right sides should be called left and right, not l and r. When you begin using a linter it is going to complain, A lot. May as well develop good habits early on.

https://www.python.org/dev/peps/pep-0008/

And don't put multiple statements on one line. Not even beak.

if len(r)==0: break