2
\$\begingroup\$

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[0] > right[0]:
            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))
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$

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.