A bunch of sort algorithms

sorts.py

from random import shuffle
import time

def generate_array(size):
    result = [i for i in range(0, size)]
    shuffle(result)
    return result

def is_in_order(a, size):
    if (len(a) != size):
        return False
    for n in range(0, size):
        if (n != a[n]):
            return False
    return True

iters=5
def test_sort(f, size=10):
    totalt = 0
    for n in range(0, iters):
        a = generate_array(size)
        t1 = time.time()
        a = f(a) # Run
        t2 = time.time()
        totalt += (t2-t1)
        
    dur = "%.1f ms" % (totalt*1000/iters)
    
    if (is_in_order(a, size)):
        print("%s ok (%s)" % (f.__name__, dur))
    else:
        print("%s ERROR (%s)" % (f.__name__, dur))

# ==========================================================

def null_sort(a):
    return a

# ==========================================================

def insertion_sort(a):
    # 0 is already sorted
    # for each element
    for n in range(1, len(a)):
        item = a[n]
        # walk backwards, shifting elements to the right
        # until you find one less than it
        for m in range(n, 0, -1):
            if (item < a[m-1]):
                a[m] = a[m-1]
            else:
                break
        else:
            m = 0

        # place the item there
        a[m] = item

    return a
    
# ==========================================================

def merge_sort(a):
    if (len(a) <= 1):
        return a

    mid = int(len(a)/2)
    left = [a[i] for i in range(0,mid)]
    left = merge_sort(left)
    right = [a[i] for i in range(mid,len(a))]
    right = merge_sort(right)

    # now merge left and right
    n = 0
    m = 0
    while (True):
        if (n < len(left) and m < len(right)):
            if (left[n] < right[m]):
                a[n+m] = left[n]
                n += 1
            else:
                a[n+m] = right[m]
                m += 1
        elif (n < len(left)):
            a[n+m] = left[n]
            n += 1
        elif (m < len(right)):
            a[n+m] = right[m]
            m += 1
        else:
            break
    
    return a

# ==========================================================

def heap_sort(a):
    def sift_down(start, end):
        while start*2+1 <= end:
            swap = start
            if a[swap] < a[start*2+1]:
                swap = start*2+1 # left child is greater
            if start*2+2 <= end and a[swap] < a[start*2+2]:
                swap = start*2+2 # right child exists and is greater

            if swap != start: # if either is greater, swap
                temp = a[start] 
                a[start] = a[swap]
                a[swap] = temp
                start = swap # and keep going downward
            else:
                return
    
    # heapify
    lastparent = int((len(a)-2)/2)
    for n in range(lastparent, -1, -1):
        sift_down(n, len(a)-1)

    for n in range(len(a)-1, -1, -1):
        # swap the first and last and re-heapify
        temp = a[0]
        a[0] = a[n]
        a[n] = temp
        sift_down(0, n-1)
        
    return a

# ==========================================================

def quick_sort(a):
    if (len(a) <= 1):
        return a

    # The pivot is the median of the first, middle, and last vals
    # Put the pivot in the 0 spot
    mid = int(len(a)/2)
    if ((a[0] < a[mid]) != (a[0] < a[-1])):
        pass
    elif ((a[0] < a[mid]) == (a[mid] < a[-1])):
        swap = a[0]
        a[0] = a[mid]
        a[mid] = swap
    else:
        swap = a[0]
        a[0] = a[-1]
        a[-1] = swap
    
    # Segment in half
    left = [i for i in a[1:] if i < a[0]]
    left = quick_sort(left)
    right = [i for i in a[1:] if i >= a[0]]
    right = quick_sort(right)
    
    return left + [a[0]] + right

# ==========================================================

for size in [16, 64, 10240]:
    print("\nn = %d" % size)
    test_sort(null_sort, size)
    test_sort(insertion_sort, size)
    test_sort(merge_sort, size)
    test_sort(heap_sort, size)
    test_sort(quick_sort, size)