sortvis.org


sorting algorithm visualisation

smoothsort

Like Timsort, smoothsort is designed to cope well with partially sorted data. The image below was generated using the same sequence as the one used for Timsort.

+
-
1:1
[ ]
drag to pan, scroll to zoom, view raw

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) * 0x077CB531L) >> 27) & 0b11111]


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


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

    if not trusty:
        sift(lst, pshift, head)


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

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

        p |= 1
        head += 1
    trinkle(lst, p, pshift, head, False)
    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)
        head -= 1

List order is sampled for visualisation whenever lst.log() is called.

Copyright 2010 Aldo Cortesi