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