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\$
  • \$\begingroup\$ Your code seems to have a bug: it doesn't include the pivot in the result. \$\endgroup\$ – Solomon Ucko Apr 4 '18 at 16:18
  • \$\begingroup\$ @SolomonUcko Thanks, not sure I follow, but I will debug tonight. \$\endgroup\$ – Chris Apr 4 '18 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\$ – Solomon Ucko Apr 4 '18 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 '18 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 '18 at 5:01
-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, privacy policy and cookie policy

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