Timsort

In informatica il Timsort è un algoritmo di ordinamento derivato dal merge sort e dall'insertion sort. La sua struttura è ottimizzata per trattare diversi tipi di dato.

Timsort
Rappresentazione grafica del Timsort: per liste brevi come quella del grafico le prestazioni del Timsort sono equivalenti a quelle del insertion sort
Classe	Algoritmo di ordinamento
Struttura dati	Array
Caso peggiore temporalmente	$\Theta (n\log n)$
Caso ottimo temporalmente	$\Theta (n)$
Caso medio temporalmente	$\Theta (n\log n)$
Caso peggiore spazialmente	$\Theta (n)$
Ottimale	Sì

Il suo nome deriva da quello del suo inventore, Tim Peters, che lo ha creato nel 2002 quale algoritmo di ordinamento standard del linguaggio di programmazione Python e di Rust, in cui è stato integrato a partire dalla versione 2.3. È anche utilizzato per ordinare i vettori in Java 7.

Collegamenti esterni

• (EN) Denis Howe, Timsort, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL