trjhtr

I am re-learning my fundamental algorithms, and have been told my Python is overly verbose.

Can you take a look at my merge sort algorithm and let me know how you would clean it up and make it more pythonic, if applicable?

def merge(left,right):
 out = 
 l_rest = 
 i = left[0]
 while i is not None:
 if right:
 if i < right[0]:
 out.append(i)
 left.remove(i)
 else:
 out.append(right[0])
 right.remove(right[0])
 else:
 out.append(i)
 left.remove(i)

 if len(left) > 0:
 i = left[0]
 else:
 i = None
 for i in l_rest:
 out.append(i)
 for i in right:
 out.append(i)
 return out

def sort(lst):
 if len(lst) == 1:
 return lst

 left = sort(lst[:len(lst)//2])
 right = sort(lst[len(lst)//2:])
 return merge(left,right)

Starting a wiki with the suggested edits in the comments so far.

def merge(left,right):
 out = 
 i = left[0]
 while i is not None:
 if right and i < right[0]:
 out.append(i)
 left.remove(i)
 else:
 out.append(right[0])
 right.remove(right[0])

 if len(left) > 0:
 i = left[0]
 else:
 i = None

 return out + left + right

def sort(lst):
 if len(lst) == 1:
 return lst

 left = sort(lst[:len(lst)//2])
 right = sort(lst[len(lst)//2:])
 return merge(left,right)