Foo

foo

import time
import random

# fill the input list
a = [random.randrange(0,130) for x in range(10**6)]

# std sort, keep a unsorted
t = time.time()
b = sorted(a)
print(time.time() - t)

# optimize all the things
t = time.time()
c = [0]*130
for x in a:
    c[x] += 1

d = [None]*10**6

i=j=0
for x in c:
    for _ in range(x):                                                                               
        d[j] = i 
        j+=1
    i+=1
print(time.time() - t)

assert(b == d)

import time
import random

# fill the input list
data = [random.randrange(0,130) for x in range(10**6)]

# std sort, keep a unsorted
def timsort(a):
    t = time.time()
    b = sorted(a)
    print("Timsort: ", time.time() - t)
    return b

# optimize all the things
def genius_sort(a):
    t = time.time()
    c = [0]*130
    for x in a:
        c[x] += 1

    d = [None]*10**6

    i = j = 0
    for x in c:
        for _ in range(x):                                                                               
            d[j] = i 
            j += 1
        i += 1

    print("Genius sort: ", time.time() - t)
    return d

def counting_sort(array, maxval):
    """in-place counting sort"""
    t = time.time()
    m = maxval + 1
    count = [0] * m
    for a in array:
        count[a] += 1
    i = 0
    for a in range(m):
        for c in range(count[a]):
            array[i] = a
            i += 1

    print("Counting sort: ", time.time() - t)
    return array

tim = timsort(data)
gen = genius_sort(data)
cou = counting_sort(data, 130)

assert(tim == gen)
assert(tim == cou)