# Merge sort a list of integers

This code is meant to sort a list of integers using merge sort.

I'm doing this to improve my style and to improve my knowledge of fundamental algorithms/data structures for an upcoming coding interview.

def merge_sort(l):
if len(l) == 0 or len(l) == 1:
return

mid = len(l) // 2
left = l[:mid]
right = l[mid:]
merge_sort(left)
merge_sort(right)
merge(l, left, right)

def merge(l, left, right):
l_ind, r_ind, ind = 0, 0, 0
left_len, right_len, l_len = len(left), len(right), len(l)

while l_ind < left_len and r_ind < right_len:
if left[l_ind] < right[r_ind]:
l[ind] = left[l_ind]
l_ind += 1
ind += 1
else:
l[ind] = right[r_ind]
r_ind += 1
ind += 1

if l_ind < left_len and r_ind >= right_len:
while ind < l_len:
l[ind] = left[l_ind]
l_ind += 1
ind += 1
elif l_ind >= left_len and r_ind < right_len:
while ind < l_len:
l[ind] = right[r_ind]
r_ind += 1
ind += 1


# Get rid of some len

left_len, right_len, l_len = len(left), len(right), len(l)


Get rid of these, they don't do anything in terms of readability. They also are unnecessary, the len call is not O(n) it is simply O(1).

# (Maybe) a library?

Also, although Rosetta code isn't always the most stylistic source, if you look at their solution, the use a pre-built merge. As you say you are "reinventing the wheel", maybe you don't want to do that but something to consider in the future.

# Naming

l_ind, r_ind ...


I would write those out in full as left_ind and right_ind.

• Thanks for the answer. I didn't know that len() was O(1). That'll definitely neaten my code up. All the suggestions were good. Thanks again :) Commented Nov 16, 2016 at 21:20