# Python Merge Sort Implementation

I doing some algorithm reviews and am soliciting opinions on my implementation of the Merge Sort in Python.

Anything from readability to optimization is fair game.

In particular, I am wondering if accessing the elements of a list using pop(0) somehow slows things down. I am doing this because I am not aware of a good way to peek into the last for the last element.

import math

def merge(left, right):

merge_result = []

while (len(left) > 0 and len(right) > 0):
if left > right:
merge_result.append(right.pop(0))
else:
merge_result.append(left.pop(0))

while (len(left)):
merge_result.append(left.pop(0))

while (len(right)):
merge_result.append(right.pop(0))

return merge_result

def merge_sort(array_to_be_sorted):

if len(array_to_be_sorted) < 2:
return array_to_be_sorted

middle = math.floor(len(array_to_be_sorted) / 2)

left = array_to_be_sorted[0:middle]
right = array_to_be_sorted[middle:]

return merge(merge_sort(left),merge_sort(right))


.pop(0) would remove the first element from a list - this is a $O(n)$ operation since everything after must "shift" (Time Complexity reference).

I would not pop from left and right subarrays and instead keep track of indexes in both the left and right lists:

def merge(left, right):
merge_result = []

left_index = right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index] > right[right_index]:
merge_result.append(right[right_index])
right_index += 1
else:
merge_result.append(left[left_index])
left_index += 1

merge_result += left[left_index:]
merge_result += right[right_index:]

return merge_result


And, if you are preparing for an interview, make sure to write this function from memory couple times - it'll persist in your memory pretty soon - focus on the pattern (using left and right indexes for merging), don't try to remember the code line-by-line.