Library sort

Library sort es un algoritmo de ordenación que usa ordenación por inserción, pero con espacios vacíos en el arreglo para acelerar inserciones subsiguientes. El nombre proviene de una analogía:Suponga que un bibliotecario almacene sus libros alfabéticamente en una estante, empezando por la A desde la izquierda, y continuando a la derecha a lo largo del estante sin espacios entre los libros hasta que termine por la Z. Si el bibliotecario adquiere un libro nuevo que pertenece a la sección B, una vez que encuentra el espacio correcto en la sección B, tiene que mover cada libro a partir de ese hasta el último libro en la sección Z para abrir espacio al libro nuevo. Esto es ordenación por inserción. Sin embargo, si dejara un espacio vacío después de cada letra, mientras hubiera un espacio vacío después de B, sólo tendría que mover unos cuantos libros para poder ubicar el nuevo libro. Esto es el principio básico de Library Sort. El algoritmo estuvo propuesto por Michael Un. Bender, Martín Farach-Colton, y Miguel Mosteiro en 2004 y estuvo publicado en 2006.​​ Como la ordenación por inserción, Library sort es un algoritmo de ordenamiento por comparación estable y puede ser corrido como un algoritmo en línea; aun así, ha mostrado tener una probabilidad alta de correr en un tiempo O(n log n) (comparable a quicksort), mejor que el tiempo de ordenación por inserción O(n2). El mecanismo utilizado para esta mejora es muy similar a aquello de un skip list.No hay una implementación completa escrita, ni los algoritmos exactos de partes importantes, como la inserción y el re-equilibrio. Sería necesaria más información para discutir cómo la eficiencia de Library sort se compara con otros métodos de ordenamiento en realidad. Comparado a la ordenación por inserción básica, la desventaja de Library sort es que requiere...