current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 1 down vote favorite

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
share|improve this question
1  
Welcome to Code Review! I hope you get some helpful answers. – SirPython Jan 28 at 0:28
up vote 1 down vote accepted

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.

share|improve this answer
    
Wow! You are completely right!! Thank you so much for the input! – Dawit Abraham Jan 31 at 21:07
up vote 2 down vote

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.

share|improve this answer
    
Thank You very much. I found it quit helpful :) – Dawit Abraham Jan 31 at 21:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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