sort_benchmark.py

import random
import timeit
from collections import defaultdict

random.seed(1)


def bucketsort(order, seq):
    buckets = [0] * (max(seq) + 1)
    for x in seq:
        buckets[x] += 1
    for i in range(len(buckets) - 1):
        buckets[i + 1] += buckets[i]

    new_order = [-1] * len(seq)
    for i in reversed(order):
        x = seq[i]
        idx = buckets[x] = buckets[x] - 1
        new_order[idx] = i

    return new_order


def ordersort(order, seq, reverse=False):
    bit = max(seq).bit_length() >> 1
    mask = (1 << bit) - 1
    order = bucketsort(order, [x & mask for x in seq])
    order = bucketsort(order, [x >> bit for x in seq])
    if reverse:
        order.reverse()
    return order


def long_ordersort(order, seq):
    order = ordersort(order, [int(i & 0x7FFFFFFF) for i in seq])
    return ordersort(order, [int(i >> 31) for i in seq])


def multikey_ordersort(order, *seqs, sort=ordersort):
    for i in reversed(range(len(seqs))):
        order = sort(order, seqs[i])
    return order


def splode_sort(x):
    n, d = len(x), defaultdict(list)
    for ri, e in enumerate(reversed(x)):
        d[e].append(n - ri - 1)
    return [d[e].pop() for e in sorted(x)]


def main():
    N = 10**5
    RUNS = 100

    def pretty_timeit(name, func):
        print(f"{name:15} {timeit.timeit(lambda: func(), number=RUNS):6.3f}s / {RUNS}")

    # < 2 ** 16
    arr = [random.randint(0, 2**16) for _ in range(N)]
    print("<= 2 ** 16")
    pretty_timeit("sorted", lambda: sorted(arr))
    pretty_timeit("getter_sort", lambda: sorted(range(N), key=arr.__getitem__))
    pretty_timeit("splode_sort", lambda: splode_sort(arr))
    pretty_timeit("bucketsort", lambda: bucketsort(range(N), arr))
    pretty_timeit("ordersort", lambda: ordersort(range(N), arr))
    pretty_timeit("long_ordersort", lambda: long_ordersort(range(N), arr))
    print()

    # < 2 ** 32
    arr = [random.randint(0, 2**32) for _ in range(N)]
    print("<= 2 ** 32")
    pretty_timeit("sorted", lambda: sorted(arr))
    pretty_timeit("getter_sort", lambda: sorted(range(N), key=arr.__getitem__))
    pretty_timeit("splode_sort", lambda: splode_sort(arr))
    # pretty_timeit("bucketsort", lambda: bucketsort(range(N), arr))
    pretty_timeit("ordersort", lambda: ordersort(range(N), arr))
    pretty_timeit("long_ordersort", lambda: long_ordersort(range(N), arr))
    print()

    # < 2 ** 62
    arr = [random.randint(0, 2**62) for _ in range(N)]
    print("<= 2 ** 62")
    pretty_timeit("sorted", lambda: sorted(arr))
    pretty_timeit("getter_sort", lambda: sorted(range(N), key=arr.__getitem__))
    pretty_timeit("splode_sort", lambda: splode_sort(arr))
    # pretty_timeit("bucketsort", lambda: bucketsort(range(N), arr))
    # pretty_timeit("ordersort", lambda: ordersort(range(N), arr))
    pretty_timeit("long_ordersort", lambda: long_ordersort(range(N), arr))
    print()

    # < 2 ** 64 (long)
    arr = [random.randint(0, 2**64) for _ in range(N)]
    print("<= 2 ** 64 (long)")
    pretty_timeit("sorted", lambda: sorted(arr))
    pretty_timeit("getter_sort", lambda: sorted(range(N), key=arr.__getitem__))
    pretty_timeit("splode_sort", lambda: splode_sort(arr))
    # pretty_timeit("bucketsort", lambda: bucketsort(range(N), arr))
    # pretty_timeit("ordersort", lambda: ordersort(range(N), arr))
    pretty_timeit("long_ordersort", lambda: long_ordersort(range(N), arr))
    print()


if __name__ == "__main__":
    main()