Implementation of merge sort in Python
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.