Samplesort: Un Enfoque de Muestreo para la Ordenación de Árboles de Almacenamiento Mínimo

Los métodos actualmente en uso y previamente propuestos para la elección de una raíz en la ordenación de árboles de almacenamiento mínimo son, en realidad, métodos para hacer estimaciones estadísticamente ineficientes de la mediana de la secuencia a ordenar. Al hacer un uso eficiente de la información en una muestra aleatoria elegida durante la entrada de la secuencia a ordenar, se pueden lograr mejoras significativas sobre la ordenación ordinaria de árboles de almacenamiento mínimo. Se propone un procedimiento que es una generalización de la ordenación de árboles de almacenamiento mínimo y que tiene las siguientes tres propiedades: (a) Hay una mejora significativa (sobre la ordenación ordinaria de árboles de almacenamiento mínimo) en el número esperado de comparaciones requeridas para ordenar la secuencia de entrada. (b) El procedimiento es estadísticamente insensible a sesgos en la secuencia de entrada. (c) El número esperado de comparaciones requeridas por el procedimiento se aproxima (lentamente) al límite inferior teórico de la información en el número de comparaciones requeridas. Por lo tanto, el procedimiento es “asintóticamente óptimo.”