Timsort

Da Wikipedia, l'enciclopedia libera.
Timsort
Step-by-step visualisation of 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

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.

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, in cui è stato integrato a partire dalla versione 2.3. È anche utilizzato per ordinare i vettori in Java 7[1].

Riferimenti[modifica | modifica wikitesto]

  1. ^ jdk7/tl/jdk: changeset 1423:bfd7abda8f79