sortvis.org


sorting algorithm visualisation

timsort

On small lists of random elements, Timsort looks just like mergesort. The image below was generated with the type of data that Timsort really shines on - a partially ordered array. This lets us see behaviours like run detection and the bulk reversal of chunks of reverse-sorted data. For more information, see my blog post on visualising timsort.

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

The Python interpreter's Timsort is implemented in C. We use a clever trick to interrupt the built-in Python sort periodically to get progressive sorting information. The canonical guide to Timsort's implementation is Tim Peter's own description of the algorithm.

code

class TimBreak(Exception): pass


class TimWrapper:
    list = None
    comparisons = 0
    limit = 0
    def __init__(self, n):
        self.n = n

    def __cmp__(self, other):
        if TimWrapper.comparisons > TimWrapper.limit:
            raise TimBreak
        TimWrapper.comparisons += 1
        return cmp(self.n, other.n)

    def __getattr__(self, attr):
        return getattr(self.n, attr)


def timsort(lst):
    lst.wrap(TimWrapper)
    TimWrapper.list = lst
    prev = [i.n for i in lst]
    while 1:
        TimWrapper.comparisons = 0
        TimWrapper.limit += 1
        lst.reset()
        try:
            lst.sort()
        except TimBreak:
            if prev != [i.n for i in lst]:
                lst.log()
                prev = [i.n for i in lst]
        else:
            lst.log()
            break

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

Copyright 2010 Aldo Cortesi