Merge sort a list of integers

Question

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

Answer 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.

• cycloidistic: 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 :)