1
\$\begingroup\$

I am re-learning my fundamental algorithms, and have been told my Python is overly verbose.
Can you take a look at my merge sort algorithm and let me know how you would clean it up and make it more pythonic, if applicable?

def merge(left,right):
    out = []
    l_rest = []
    i = left[0]
    while i is not None:
        if right:
            if i < right[0]:
                out.append(i)
                left.remove(i)
            else:
                out.append(right[0])
                right.remove(right[0])
        else:
            out.append(i)
            left.remove(i)

         if len(left) > 0:
             i = left[0]
         else:
             i = None
    for i in l_rest:
        out.append(i)
    for i in right:
        out.append(i)
    return out

def sort(lst):
    if len(lst) == 1:
        return lst

    left = sort(lst[:len(lst)//2])
    right = sort(lst[len(lst)//2:])
    return merge(left,right)
\$\endgroup\$
5
  • \$\begingroup\$ Your code seems to have a bug: it doesn't include the pivot in the result. \$\endgroup\$ Apr 4, 2018 at 16:18
  • \$\begingroup\$ @SolomonUcko Thanks, not sure I follow, but I will debug tonight. \$\endgroup\$
    – Chris
    Apr 4, 2018 at 16:49
  • \$\begingroup\$ Sorry, at first I thought it was quicksort. What I meant was that, for example, if I sort a list of the numbers 0-99, repeated 100 times, then shuffled, the 0s are missing. \$\endgroup\$ Apr 4, 2018 at 17:01
  • 1
    \$\begingroup\$ why not just out += l_rest + right instead of for i in l_rest: out.append(i); for i in right: out.append(i) \$\endgroup\$
    – Yulia V
    Apr 4, 2018 at 18:21
  • \$\begingroup\$ @SolomonUcko fixed, that was nasty. Thanks. I chose to fix that and not fix YuliaV's suggestion inline... Not sure the best practice for implementing incremental improvements, but I like their idea. \$\endgroup\$
    – Chris
    Apr 5, 2018 at 5:01

1 Answer 1

-1
\$\begingroup\$

Starting a wiki with the suggested edits in the comments so far.

def merge(left,right):
    out = []
    i = left[0]
    while i is not None:
        if right and i < right[0]:
            out.append(i)
            left.remove(i)
        else:
            out.append(right[0])
            right.remove(right[0])

         if len(left) > 0:
             i = left[0]
         else:
             i = None

    return out + left + right

def sort(lst):
    if len(lst) == 1:
        return lst

    left = sort(lst[:len(lst)//2])
    right = sort(lst[len(lst)//2:])
    return merge(left,right)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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