On the Worst-Case Complexity of TimSort

Nicolas Auger, Vincent Jugé, Cyril Nicaud +1

TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint. In fact, there are two…