# smoothsort

## code

``````# Possibly replace with a generator that produces Leonardo numbers?
# That would be of limited utility since this is all of them up to 31 bits.
LP = [ 1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973,
3193, 5167, 8361, 13529, 21891, 35421, 57313, 92735, 150049, 242785,
392835, 635621, 1028457, 1664079, 2692537, 4356617, 7049155,
11405773, 18454929, 29860703, 48315633, 78176337, 126491971,
204668309, 331160281, 535828591, 866988873 ]

# Solution for determining number of trailing zeroes of a number's binary representation.
# Taken from http://www.0xe3.com/text/ntz/ComputingTrailingZerosHOWTO.html
# I don't much like the magic numbers, but they really are magic.
MultiplyDeBruijnBitPosition = [ 0,  1, 28,  2, 29, 14, 24, 3,
30, 22, 20, 15, 25, 17,  4, 8,
31, 27, 13, 23, 21, 19, 16, 7,
26, 12, 18,  6, 11,  5, 10, 9]

def trailingzeroes(v):
return MultiplyDeBruijnBitPosition[(((v & -v) * 0x077CB531) >> 27) & 0b11111]

while pshift > 1:
lf = head - 1 - LP[pshift - 2]
break
if lst[lf] >= lst[rt]:
pshift -= 1
else:
pshift -= 2
lst.log()

def trinkle(lst, p, pshift, head, trusty):
while p != 1:
break
if not trusty and pshift > 1:
lf = head - 1 - LP[pshift - 2]
if lst[rt] >= lst[stepson] or lst[lf] >= lst[stepson]:
break
lst.log()
trail = trailingzeroes(p & ~1)
p >>= trail
pshift += trail
trusty = False

if not trusty:

def smoothsort(lst):
p = 1
pshift = 1
while head < len(lst) - 1:
if (p & 3) == 3:
p >>= 2
pshift += 2
else:
if LP[pshift - 1] >= len(lst) - 1 - head:
else:

if pshift == 1:
p <<= 1
pshift -= 1
else:
p <<= pshift - 1
pshift = 1

p |= 1
while pshift != 1 or p != 1:
if pshift <= 1:
trail = trailingzeroes(p & ~1)
p >>= trail
pshift += trail
else:
p <<= 2
p ^= 7
pshift -= 2

trinkle(lst, p >> 1, pshift + 1, head - LP[pshift] - 1, True)
trinkle(lst, p, pshift, head - 1, True)
List order is sampled for visualisation whenever `lst.log()` is called.