Timsort

Timsort es un algoritmo híbrido (Merge e Inserción) que Tim Peters publicó para el lenguaje Python en 2.002, Joshua Bloch lo incorporó a los métodos java.util.Collections.sort y java.util.Arrays.sort pero poco después, en 2.012, Nicolas Auger, Vincent Jugé, Cyril Nicaud y Carine Pivoteau descubrieron que la versión en Collections.sort se “colgaba” con determinadas condiciones. En 2.015 Stijn de Gouw, Jurriaan Rot, Frank S. de Boer, Richard Bubel y Reiner Hähnle diseñaron correcciones para el algoritmo y en Java versión 8 ya están operativas.

 

Rendimiento – Complejidad
Mejor caso Ω	Peor caso O	Media Θ	Espacio
(n)	(n log n)	(n log n)	(n)
En Python por Auger, Jugé, Nicaud y  Pivoteau. H es la entropía de la distribución de ejecuciones (secuencias monotónicas máximas)	1,5nH + O(n)

 

Los subvectores son la pieza sobre la que se fundamenta el algoritmo. El primer paso comienza con la elección del tamaño (salto) que tendrán los subvectores, en el ejemplo 1.024 elementos.

Por otro lado, el algoritmo está diseñado pensando que los datos están parcialmente ordenados, de esta forma realiza un primer recorrido (salto a salto) a través del vector en busca de un subvector que contenga dos elementos contiguos ordenados (ascendente o descendente), intercambiándolos si no están en el orden que nos interesa.

La elección de la división del vector, en subvectores, radica en la posibilidad de ordenar los mismos a través de la ordenación por inserción binaria, muy rápida para vectores de pequeño tamaño, utilizando la fusión (Merge) cuando los saltos superan al tamaño del vector original.

 

Ejemplo.

 

public static int[] OrdenaTim(int[] Vector) {
    int tamañoV = Vector.length;
    int tamañosubV = 0;
    if (tamañoV > 2048)	tamañosubV = (int) tamañoV / 1024;
    else				tamañosubV = 100;

    for (int i = 0; i < tamañoV; i += tamañosubV) {
      timinserciónB(Vector, i, Math.min((i + tamañosubV - 1), (tamañoV - 1)));
    }

    for (int tamañoM = tamañosubV; tamañoM < tamañoV; tamañoM = 2 * tamañoM) {
      for (int izquierda = 0; izquierda < tamañoV; izquierda += 2 * tamañoM) {
        int medio = izquierda + tamañoM - 1;
        int derecha = Math.min((izquierda + 2 * tamañoM - 1), (tamañoV - 1));
        if (medio<=derecha) timmerge(Vector, izquierda, medio, derecha);
      }
    }
    return Vector;
  }
      

  public static void timinserciónB(int[] Vector, int izquierda, int derecha) {
    for (int i = izquierda + 1; i <= derecha; i++) {
      int intercambio = Vector[i];
      int j = i - 1;
      while (Vector[j] > intercambio && j >= izquierda) {
        Vector[j + 1] = Vector[j];
        j--;
        if (j < 0)	break;
      }
      Vector[j + 1] = intercambio;
    }
  } 
  

  public static void timmerge(int[] Vector, int izquierda, int medio, int derecha) {
    int tamañoizq = medio - izquierda + 1;
    int tamañoder = derecha - medio;
    int[] tempizq = new int[tamañoizq];
    int[] tempder = new int[tamañoder];
    
    for (int x = 0; x < tamañoizq; x++) tempizq[x] = Vector[izquierda + x];
    for (int x = 0; x < tamañoder; x++) tempder[x] = Vector[medio + 1 + x];

    int i = 0;
    int j = 0;
    int k = izquierda;

    while (i < tamañoizq && j < tamañoder) {
      if (tempizq[i] <= tempder[j]) {
        Vector[k] = tempizq[i];
        i++;
      } else {
        Vector[k] = tempder[j];
        j++;
      }
      k++;
    }

    while (i < tamañoizq) {
      Vector[k] = tempizq[i];
      k++;
      i++;
    }

    while (j < tamañoder) {
      Vector[k] = tempder[j];
      k++;
      j++;
    }
  }

Rendimiento.

Estadística individual realizada con el mismo equipo y condiciones del resumen de estadísticas de ordenación. Se ve como en la ordenación parcial es más eficiente que en el resto de ordenaciones (no en orden ascendente y en sierra).