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.
[1][2] 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.
En cada ronda insertamos tantos elementos como hayan, en el arreglo, antes del re-equilibrio de este.
Para encontrar la posición donde insertar, aplicamos Búsqueda Binaria en el arreglo y entonces intercambiamos los elementos siguientes hasta que damos con un espacio vacío.
Esto puede ser hecho moviéndose por las partes izquierda o derecha de forma recursiva y viendo si encontramos un espacio vacío en el medio.