Playing with the walrus operator, I have this implementation of merge sort:
def mergesort(array):
if len(array) == 1:
output = array
else:
pivot = len(array) // 2
left = mergesort(array[pivot:])
right = mergesort(array[:pivot])
output = []
while (l := len(left)) or (r := len(right)):
if l and r and left[0] < right[0]:
output.append(left.pop(0))
elif r:
output.append(right.pop(0))
else:
output.append(left.pop(0))
return output
mergesort([66, 93, 85, 46, 56, 88, 56, 75, 55, 99, 87])
But this returns the error UnboundLocalError: local variable 'r' referenced before assignment:
---------------------------------------------------------------------------
UnboundLocalError Traceback (most recent call last)
/tmp/ipykernel_134/1678992391.py in <module>
----> 1 mergesort(array)
/tmp/ipykernel_134/4030760045.py in mergesort(array)
5 else:
6 pivot = len(array) // 2
----> 7 left = mergesort(array[pivot:])
8 right = mergesort(array[:pivot])
9
...
/tmp/ipykernel_134/4030760045.py in mergesort(array)
10 output = []
11 while (l := len(left)) or (r := len(right)):
---> 12 if l and r and left[0] < right[0]:
13 output.append(left.pop(0))
14 elif r:
UnboundLocalError: local variable 'r' referenced before assignment
Why isn't r included in my for loop, while l is?
Boolean OR or is lazy, so when l turns out to be true, (r := len(right)) doesn't even get executed.
You could use the non-lazy bitwise OR | in this case, although it's a bit of an abuse.
Or just use the truth value of the lists instead of their lengths:
while left or right:
if left and right and left[0] < right[0]:
output.append(left.pop(0))
elif right:
output.append(right.pop(0))
else:
output.append(left.pop(0))
Btw better use <= instead of <, so that it's a stable sort as mergesort ought to be.
Addendum: Having fun with laziness:
while left or right:
which = (left or right)[0] <= (right or left)[0] and left or right
output.append(which.pop(0))
Another, note I switched to while ... and ... and append the remaining non-empty one after the loop:
while left and right:
which = left if left[0] <= right[0] else right
output.append(which.pop(0))
output += left or right
Or back to your style:
while left and right:
if left[0] <= right[0]:
output.append(left.pop(0))
else:
output.append(right.pop(0))
output.extend(left or right)