2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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 :) \$\endgroup\$ – cycloidistic Nov 16 '16 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.