Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Paul and Simon Sort
# "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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment