#!/usr/bin/env python
from sys import maxsize as UNENDLICH

def teil_array (X,von,bis):
    return X[von: bis+1] + [UNENDLICH]

def von_bis (von,bis):
    return range(von,bis+1)

def MergeSort (array):

    def Merge (p,q,r):
        # print ("Running Merge(%d,%d,%d)" % (p,q,r))
        L = teil_array(A,p,q)
        R = teil_array(A,q+1,r)
        i = 0; j = 0
        for k in von_bis(p,r):
            if L[i] <= R[j]:
                A[k] = L[i]
                i = i+1
            else:
                A[k] = R[j]
                j = j+1

    def MergeSortRec (p,r):
        if p<r:
            q = (p+r) // 2   #  // = Integer-Division
            MergeSortRec (p,q)
            MergeSortRec (q+1,r)
            Merge(p,q,r)

    A = array[:]  # Kopie anlegen
    MergeSortRec (0, len(A)-1)
    return A

X = [9, 1, 3, 4, 2, 8, 10, 0]
Y = MergeSort (X)

print ("Vorher:  ", X)
print ("Nachher: ", Y)