2
\$\begingroup\$

I was working on an assignment and I was hoping to know if the merge sort algorithm I wrote in Python was not making any unnecessary computations.

def sort(some_list):

    if len(some_list) > 1:
        return merge(sort(some_list.__getslice__(0, len(some_list)/2)),\
         sort(some_list.__getslice__(len(some_list)/2, len(some_list))))
    else:
        return some_list


def merge(list_left, list_right):

    sorted_list = []

    while len(list_left) > 0 or len(list_right) > 0:

        if len(list_left) == 0:
            sorted_list.append(list_right.pop(0))

        elif len(list_right) == 0:
            sorted_list.append(list_left.pop(0))

        elif list_left[0] < list_right[0]:
            sorted_list.append(list_left.pop(0))

        else:
            sorted_list.append(list_right.pop(0))
    return sorted_list

I did some testing by calling time function to check how much time it took to merge a list of numbers of size 100,000 with different presortedness values (where a presortedness = 0 means it's completely random and presortedness = 1 means the list is already sorted).

I'm using a core i7 processor and working from PyCharm on an Ubuntu 14.04 OS.

This was my result:

-------Test for Merge Sort----------------
Presortedness = 0.00 (completely random)
Time elapsed = 1.90153600 


Presortedness = 0.25
Time elapsed = 1.89535800 


Presortedness = 0.50
Time elapsed = 1.90894200 


Presortedness = 0.75
Time elapsed = 1.90660100 


Presortedness = 1.00 (sorted)
Time elapsed = 1.79297100
\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to Code Review! I hope you get some helpful answers. \$\endgroup\$ – SirPython Jan 28 '16 at 0:28
2
\$\begingroup\$

It is actually a terribly inefficient implementation... Some things to keep in mind:

  1. Do not use the __getslice__ method explicitly. It is a relic of a time long gone, and you only need to know about it if subclassing objects written in CPython. Not your case. And your code can be written in an infinitely more readable form as:

    def sort(some_list):
        if len(some_list) > 1:
           return merge(sort(some_list[:len(some_list)/2],
                         sort(some_list[len(some_list)/2:]))
        else:
            return some_list
    
  2. Slicing a Python list creates a copy of the list. This is not what you typically want in a merge sort. To avoid this, you can leave your original list unsliced, and pass around indices to the intervals being sorted and merged. Such an in-place merge sort could be written as:

    def sort(list_, lo=None, hi=None):
        if lo is None:
            lo = 0
        if hi is None:
            hi = len(list_)
        if hi - lo <= 1:
            return
        mid = lo + (hi - lo) // 2
        sort(list_, lo, mid)
        sort(list_, mid, hi)
        merge(list_, lo, mid, hi)
    
    def merge(list_, lo, mid, hi):
        temp = list_[lo:mid]
        left = 0
        right = mid
        write = 0
        while left < mid - lo and right < hi:
            if list_[right] < temp[left]:
                list_[write] = list_[right]
                right += 1
            else:
                list_[write] = temp[left]
                left += 1
            write += 1
        if left < mid - lo
            list_[write:] = temp[left:]
    

    This is not a very Pythonic implementation. It actually looks like C or Java translated line by line into Python. But there is not much way around it. Unless you simply do sort(list_), which is the Pythonic way of getting a listy sorted.

\$\endgroup\$
  • \$\begingroup\$ Wow! You are completely right!! Thank you so much for the input! \$\endgroup\$ – Dawit Abraham Jan 31 '16 at 21:07
2
\$\begingroup\$

The main thing I see here is the constant use of '.pop' from array. You should try to avoid that because it moves (shifts) items in the array each time. I suggest avoiding changing the array at all.

Instead of

#you read the len of some_list 3 times.
some_list.__getslice__(0, len(some_list)/2)
some_list.__getslice__(len(some_list)/2, len(some_list))     

I would use

mid = len(some_list) // 2  # measures the size of the list once for large lists
some_list[:mid] # left half
some_list[mid:] # right half
# makes your code more readable.

You can take these two out of the loop

if len(list_left) == 0:
   sorted_list.append(list_right.pop(0))

elif len(list_right) == 0:
   sorted_list.append(list_left.pop(0))

and add the rest of the larger list to the sorted_list and then change the condition of your loop to 'and' instead of 'or'.

Side Note: I have seen other developers use '.extend()' and avoid using append and pop, but I'm not sure about performance implications using it that way.

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