Implementation of merge sort in Python 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) &gt; 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) &gt; 0 or len(list_right) &gt; 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] &lt; 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
It is actually a terribly inefficient implementation... Some things to keep in mind:


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) &gt; 1:
       return merge(sort(some_list[:len(some_list)/2],
                     sort(some_list[len(some_list)/2:]))
    else:
        return some_list

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 &lt;= 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 &lt; mid - lo and right &lt; hi:
        if list_[right] &lt; temp[left]:
            list_[write] = list_[right]
            right += 1
        else:
            list_[write] = temp[left]
            left += 1
        write += 1
    if left &lt; 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.