'''
This code was written in 15-113 lecture on Tue 17-Jan and Thu 19-Jan.
It is only for demonstrational purposes, and may contain
dubious style and even an occasional bug.
'''

import timeit, random, copy, heapq

def quicksort(L):
    if (len(L) < 2):
        return L
    else:
        first = L[0]  # pivot
        rest = L[1:]
        lo = [x for x in rest if x < first]
        hi = [x for x in rest if x >= first]
        return quicksort(lo) + [first] + quicksort(hi)

def merge(A, B):
    # iterative and destructive, but practical...
    C = [ ]
    i = j = 0
    while ((i < len(A)) or (j < len(B))):
        if ((j == len(B)) or ((i < len(A)) and (A[i] <= B[j]))):
            C.append(A[i])
            i += 1
        else:
            C.append(B[j])
            j += 1
    return C

def mergesort(L):        
    if (len(L) < 2):
        return L
    else:
        mid = len(L)//2
        left = mergesort(L[:mid])
        right = mergesort(L[mid:])
        return merge(left, right)

def radixSort(L):
    largest = max(L)
    digitSelector = 1
    while digitSelector <= largest:
        zeros = [v for v in L if (v & digitSelector == 0)]
        ones  = [v for v in L if (v & digitSelector != 0)]
        L = zeros + ones
        digitSelector <<= 1
    return L

def builtinSort(L):
    return sorted(L)

def testSortFn(sizes, sortFn):
    print(f'Testing {sortFn.__name__}...')
    runtimes = [ ]
    for N in sizes:
        L = [random.randrange(10**10) for _ in range(N)]
        M = copy.copy(L)
        runtime = timeit.timeit(lambda: sortFn(L), number=1)
        runtimes.append(runtime)
    return runtimes

def findSortFns():
    sortFns = [ ]
    for fnName in globals():
        try:
            fn = globals()[fnName]
            L = [random.randrange(10**10) for _ in range(20)]
            M = fn(copy.copy(L))
            if (M == sorted(L)):
                sortFns.append(fn)
        except:
            pass
    return sortFns

import matplotlib.pyplot as plt

def timeSortFns():
    sizes = [10**k for k in range(1,6)]
    print(sizes)
    sortFns = findSortFns()
    for sortFn in sortFns:
        runtimes = testSortFn(sizes, sortFn)
        xdata = sizes
        ydata = runtimes
        plt.plot(xdata, ydata, label=sortFn.__name__)
        plt.legend()
        plt.xlabel('N (size of list)')
        plt.ylabel('Runtime (seconds)')
        plt.title('Runtime Comparison of Sorts')
    plt.show()

def heapPush(heap, value):
    heap.append(value)
    i = len(heap)-1
    while i > 0:
        iParent = (i-1)//2
        if heap[iParent] <= heap[i]:
            return
        heap[iParent], heap[i] = heap[i], heap[iParent]
        i = iParent

def heapPop(heap):
    if len(heap) == 1: return heap.pop()
    if len(heap) == 0: raise Exception('Go away')
    result = heap[0]
    heap[0] = heap.pop()
    i = 0
    while True:
        child1 = 2*i+1
        child2 = 2*i+2
        if child1 >= len(heap): break
        if ((child2 >= len(heap)) or
            (heap[child1] <= heap[child2])):
            smallerChild = child1
        else:
            smallerChild = child2
        if heap[i] <= heap[smallerChild]: break
        heap[i], heap[smallerChild] = heap[smallerChild], heap[i]
        i = smallerChild
    return result

def heapSort(L):
    heap = [ ]
    for v in L: heapPush(heap, v)
    result = [ ]
    while heap: result.append(heapPop(heap))
    return result

def mostlyBuiltinHeapSort(L):
    heap = [ ]
    for v in L: heapq.heappush(heap, v)
    result = [ ]
    while heap: result.append(heapq.heappop(heap))
    return result

timeSortFns()