Merge Sort:

 def Merge(left,right,A):
    i=j=k=0
    nl = len(left)
    nr = len(right)
    while(i<nl and j<nr):
        if left[i]<=right[j]:
            A[k] = left[i]
            k+=1
            i+=1
        else:
            A[k] = right[j]
            k+=1
            j+=1
    while i<nl:
        A[k] = left[i]
        k+=1
        i+=1
    while j<nr:
        A[k] = right[j]
        k+=1
        j+=1
    return A


def MergeSort(A):
    n = len(A)
    if n<2:
        return
    mid = n/2
    left = A[:mid]
    right = A[mid:]

    MergeSort(left)
    MergeSort(right)
    Merge(left,right,A)

A=[4,5,3,2,1]
MergeSort(A)
print A

Time Complexity: O(n logn)