Timsort

algoritmo di ordinamento derivato dal merge sort e dall'insertion sort

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
ClasseAlgoritmo di ordinamento
Struttura datiArray
Caso peggiore temporalmente
Caso ottimo temporalmente
Caso medio temporalmente
Caso peggiore spazialmente
Ottimale

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[1].

  1. ^ jdk7/tl/jdk: changeset 1423:bfd7abda8f79, su hg.openjdk.java.net. URL consultato il 17 maggio 2010 (archiviato dall'url originale il 28 febbraio 2012).

Collegamenti esterni

modifica
  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica