6
\$\begingroup\$

I'm very new to python, however not new to programming as I've been doing C for some time.

So here is my practice of a merge sort, I looked at other questions however they were many more lines compared to mine. Which leaves me to believe I'm doing something wrong.

I come here to look for best practices in python, and I mean the best of the best. I want to know all the little details! Most importantly if there is anyway to shorten code without sacrificing efficiency.

#!/usr/bin/python

def merge_sort(array):
    ret = []
    if( len(array) == 1):
        return array;
    half  = len(array) / 2
    lower = merge_sort(array[:half])
    upper = merge_sort(array[half:])
    lower_len = len(lower)
    upper_len = len(upper)
    i = 0
    j = 0
    while i != lower_len or j != upper_len:
        if( i != lower_len and (j == upper_len or lower[i] < upper[j])):
            ret.append(lower[i])
            i += 1
        else:
            ret.append(upper[j])
            j += 1

    return ret

array = [4, 2, 3, 8, 8, 43, 6,1, 0]
ar = merge_sort(array)
print " ".join(str(x) for x in ar)
#>>> 0 1 2 3 4 6 8 8 43

Thanks CR.

\$\endgroup\$
7
\$\begingroup\$

First of all, there is a bug in the code - if an array is empty, you'll get a "maximum recursion depth exceeded" error. Improve your base case handling:

if len(array) <= 1:
    return array

Other improvements:

  • the merging logic can be simplified - loop while where are elements in both arrays and append what is left after the loop
  • extract the merging logic into a separate merge() function
  • improve the variable naming - e.g. use left_index and right_index as opposed to i and j, result instead of ret
  • no need to enclose if conditions into outer parenthesis
  • Python 3 compatibility:
    • use print() as a function instead of a statement
    • use // for the floor division

Improved version:

def merge(left, right):
    """Merge sort merging function."""

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

    result += left[left_index:]
    result += right[right_index:]
    return result


def merge_sort(array):
    """Merge sort algorithm implementation."""

    if len(array) <= 1:  # base case
        return array

    # divide array in half and merge sort recursively
    half = len(array) // 2
    left = merge_sort(array[:half])
    right = merge_sort(array[half:])

    return merge(left, right)
\$\endgroup\$
  • 1
    \$\begingroup\$ This is also about 20% faster with pypy (similar on Cpython \$\endgroup\$ – Oscar Smith Apr 5 '18 at 19:17
  • \$\begingroup\$ what about the slice operation complexity? I think is O(k). \$\endgroup\$ – llazzaro May 1 '18 at 19:34

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.