Paul and Simon Sort

paul_and_simon_sort.py

# "Paul-and-Simon sort"
# http://fouryears.eu/2017/07/25/sorting-in-linear-time/
# http://www-wjp.cs.uni-saarland.de/publikationen/PS80.pdf
#
# Copyright 2017, Konstantin Tretyakov
# License: MIT
 
from math import log2, ceil

def paul_and_simon_sort(a):
    n, bits = len(a), max([ceil(log2(x)) for x in a])
    temp, mask, A, B, result = 0, 0, 0, 0, 0
    
    for x in a:
        temp = (temp<<(n*(bits+1))) + (1<<bits) + x
    for i in range(n):
        A = (A<<(bits+1)) + temp
    
    temp = 0
    for x in a: 
        temp = (temp<<(bits+1)) + x
    for i in range(len(a)): 
        B = (B<<((bits+1)*n)) + temp
    
    x = A-B >> bits
    for i in range(n): 
        mask = (mask<<(n*(bits+1))) + 1
    for i in range(n):
        result += x & mask
        x = x >> (bits+1)
    
    r = [result >> (n*(bits+1)*(n-i-1)) & ((1<<(n*(bits+1)))-1) 
                                        for i in range(n)]
    a_sorted = [None]*n
    for i in range(n): 
        a_sorted[r[i]-1] = a[i]
    return a_sorted