import random 
import time
import matplotlib.pyplot as plt

def selection_sort(L):
    unsorted = L[:]
    result = []

    while unsorted:
        e = min(unsorted)
        unsorted.remove(e)
        result.append(e)

    return result

def merge(A, B):
    n = len(A) + len(B)
    C = n * [None]
    a, b = 0, 0
    for c in range(n):
        if a < len(A) and (b == len(B) or A[a] < B[b]):
            C[c] = A[a]
            a = a + 1
        else:
            C[c] = B[b]
            b = b + 1
    return C

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

def merge_sort_iterative(L):
    Q = [[x] for x in L]
    while len(Q) > 1:
        Q.insert(0, merge(Q.pop(), Q.pop()))
    return Q[0]

from collections import deque

def merge_sort_deque(L):
    Q = deque([[x] for x in L])
    while len(Q) > 1:
        Q.appendleft(merge(Q.pop(), Q.pop()))
    return Q[0]

def quicksort(L):
    if len(L) <= 1:
        return L[:]

    idx = random.randint(0,len(L)-1)
    pivot = L[idx]
    other = L[:idx] + L[idx+1:]

    small = [e for e in other if e < pivot]
    large = [e for e in other if e >= pivot]

    return quicksort(small) + [pivot] + quicksort(large)

def time_function(f, *args):
    start = time.time()
    f(*args)
    end = time.time()
    return end - start

L = [random.random() for _ in range(2**25)]
handles = []

plt.title("Sorting algorithms")
plt.xscale("log")
plt.yscale("log")

for name, algorithm, max_x in [
    ("Selection Sort", selection_sort, 16),
    ("Merge Sort", merge_sort, 22),
    ("Merge Sort (iterative)", merge_sort_iterative, 20),
    ("Merge Sort (deque)", merge_sort_deque, 22),
    ("Quicksort", quicksort, 22),
]:
    
    print(name)
    out = []
    for x in range(10, max_x+1):
        n = 2**x
        t = time_function(algorithm, L[:n])
        print(x, t)
        out.append((n,t))

    handle, = plt.plot(*zip(*out), label=name)
    plt.plot(*zip(*out), "k.", label=name)
    handles.append(handle)

plt.legend(handles=handles, loc=2)
plt.show()