Merge Sort Implementation and Optimization

Question

This is Merge Sort that i implemented, i feel i can make it better esp the combination function.

So i split the code into functions because i don't like seeing a bunch of spaghetti code in a single function. I have the combination logic which combines the left and right array such lower elements go first.

def combine(left:list, right:list): #Combines both paths
 left.append(float('inf')) #So the Array is never empty
 right.append(float('inf')) #and the final element to compare is large
 combined_list = []
 while len(left) !=1 or len(right) != 1:
 if left[0] < right[0]:
 combined_list.append(left.pop(0))
 else:
 combined_list.append(right.pop(0))
 return combined_list

Next i have this recursive function which calls itself and combination logic then after reducing the array into singular pieces then returns the bigger sorted chunks and hence final array is hence sorted.

def merge_sort(array:list):
 half_length = len(array)//2
 left = array[:half_length]
 right = array[half_length:]
 if len(left) > 1:
 left = merge_sort(left)
 if len(right) > 1:
 right = merge_sort(right)
 
 return combine(left, right)
print(merge_sort([1,2,8,5,2,4,6,9,4,2]))

I feel that left.append(float('inf')) is a hack around, is there a better way of doing it spiting it into functions.

Answer 1

• pop(0) has a linear time complexity, which makes the entire time complexity quadratic.

• The single most important advantage of merge sort is stability: the elements compare equal retain their original order. In your code, if two elements are equal the one from the right is merged first, and stability is lost.

• LeMaRk: Thanks for review, but how do i get about removing the first element from the list while mutation it, should use combined_list.append(list[0]) and list=list [1:] or is there a better way.
• vnp: Use indices. combined_list.append(list[i]) and i += 1

Answer 2

I understand what you're doing with float('inf'). Here is a possible way to make it a bit cleaner and more straightforward. Consider the following function:

def combine(left: list, right: list) -> list: 
 combined_list = []
 
 # non-empty/non-empty case
 # - results in empty/non-empty OR non-empty/empty case
 while len(left) > 0 and len(right) > 0: 
 if left[0] < right[0]:
 combined_list.append(left.pop(0))
 else:
 combined_list.append(right.pop(0))
 
 # empty/non-empty case OR empty/empty case
 # - One of these will be empty so extending by it will do nothing
 # - The other will have sorted items remaining that belong at the end of 
 # the combined list anyway.
 # - If they are both empty this will simply do nothing.
 combined_list.extend(left)
 combined_list.extend(right)
 
 return combined_list

The resulting function is bit more straightforward in my opinion. Perhaps you'll agree.