Merge Sort (My Favorite)

def mergesort(lst, first=0, last=None):
    if last == None:
        last = len(lst)
    #split the list in half
    if last - first <= 1:
        return
    mid = first + (last - first) / 2
    #run mergesort on each half
    mergesort(lst, first, mid)
    mergesort(lst, mid, last)
    #create a temp array with mid - first number of elements
    temp = range(mid - first)
    #and copy left half into temp
    for x in range(mid - first):
        temp[x] = lst[first + x]
    sp = first
    right = mid
    left = 0
    #compare smallest elements from left half and right half
    #put the smallest element in the next spot in the list
    while left < len(temp) and right < last:
        if lst[right] < temp[left]:
            lst[sp] = lst[right]
            right += 1
        else:
            lst[sp] = temp[left]
            left += 1
        sp += 1
    #copy any remaining elements from temp into the end of the array
    while left < len(temp):
        lst[sp] = temp[left]
        left += 1
        sp += 1
Advertisements