Séminaire

Abstract: Twenty years ago was invented Timsort, a surprisingly efficient sorting algorithm. One crucial aspect of Timsort is that it sorts presorted arrays (rare if array entries are elements of a large set chosen uniformly at random, but frequent in practice) in much fewer than the N log(N) operations that might be expected. We will present the algorithm and adequate measures of presortedness, explain why Timsort is so good on presorted data, and how one may still improve upon Timsort and on some of its most naive implementations.