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.
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.
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