b'\n_START_ARTICLE_\nLibrary sort\n_START_PARAGRAPH_\nLibrary sort es un algoritmo de ordenaci\xc3\xb3n que usa ordenaci\xc3\xb3n por inserci\xc3\xb3n, pero con espacios vac\xc3\xados en el arreglo para acelerar inserciones subsiguientes. El nombre proviene de una analog\xc3\xada:_NEWLINE_Suponga que un bibliotecario almacene sus libros alfab\xc3\xa9ticamente 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\xc3\xb3n B, una vez que encuentra el espacio correcto en la secci\xc3\xb3n B,  tiene que mover cada libro a partir de ese hasta el \xc3\xbaltimo libro en la secci\xc3\xb3n Z para abrir espacio al libro nuevo. Esto es ordenaci\xc3\xb3n por inserci\xc3\xb3n. Sin embargo, si dejara un espacio vac\xc3\xado despu\xc3\xa9s de cada letra, mientras hubiera un espacio vac\xc3\xado despu\xc3\xa9s de B, s\xc3\xb3lo tendr\xc3\xada que mover unos cuantos libros para poder ubicar el nuevo libro. Esto es el principio b\xc3\xa1sico de Library Sort._NEWLINE_El algoritmo estuvo propuesto por Michael Un. Bender, Mart\xc3\xadn Farach-Colton, y Miguel Mosteiro en 2004 y estuvo publicado en 2006.\xe2\x80\x8b\xe2\x80\x8b_NEWLINE_Como la ordenaci\xc3\xb3n por inserci\xc3\xb3n, Library sort es un algoritmo de ordenamiento por comparaci\xc3\xb3n estable  y puede ser corrido como un algoritmo on-line; aun as\xc3\xad, ha mostrado tener una probabilidad alta de correr en un tiempo O(n log n) (comparable a quicksort), mejor que el tiempo de ordenaci\xc3\xb3n por inserci\xc3\xb3n  O(n2). El mecanismo utilizado para esta mejora es muy similar a aquello de un skip list.No hay una implementaci\xc3\xb3n completa escrita, ni los algoritmos exactos de partes importantes, como la inserci\xc3\xb3n y el re-equilibrio. Ser\xc3\xada necesaria m\xc3\xa1s informaci\xc3\xb3n para discutir c\xc3\xb3mo la eficiencia de Library sort se compara con otros m\xc3\xa9todos de ordenamiento en realidad._NEWLINE_Comparado a la ordenaci\xc3\xb3n por inserci\xc3\xb3n b\xc3\xa1sica, la desventaja de Library sort es que requiere espacio extra para los espacios vac\xc3\xados. La cantidad y la distribuci\xc3\xb3n del espacio extra depende de la implementaci\xc3\xb3n. En principio, la medida del arreglo necesitada es (1 + \xce\xb5)n, pero sin recomendaciones de c\xc3\xb3mo escoger \xce\xb5.\xe2\x80\x8b_NEWLINE_Una debilidad de ordenaci\xc3\xb3n por inserci\xc3\xb3n es que puede requerir un n\xc3\xbamero alto de operaciones de intercambio y ser costoso si la memoria de escritura es costosa. Library sort puede mejorar un poco en el paso de inserci\xc3\xb3n, mientras necesite mover menos elementos para abrir el espacio, pero tambi\xc3\xa9n est\xc3\xa1 a\xc3\xb1adiendo un sobrecosto en el paso de re-equilibrio. Adem\xc3\xa1s, la ubicaci\xc3\xb3n de las referencias ser\xc3\xa1 pobre comparado a mergesort ya que cada inserci\xc3\xb3n de un conjunto de datos aleatorio puede acceder a memoria que ya no est\xc3\xa1 en la cache, especialmente con conjuntos de datos grande.\n_START_SECTION_\nAlgoritmo\n_START_PARAGRAPH_\nTenemos una arreglo de n elementos. Escogemos el tama\xc3\xb1o de espacio vac\xc3\xado que pretendemos dar. Entonces tendr\xc3\xadamos una arreglo de medida (1 + \xce\xb5)n. El algoritmo trabaja_NEWLINE_en log n rondas. En cada ronda insertamos tantos elementos como hayan, en el arreglo, antes del re-equilibrio de este. Para encontrar la posici\xc3\xb3n donde insertar,  aplicamos B\xc3\xbasqueda Binaria en el arreglo y entonces intercambiamos los_NEWLINE_elementos siguientes hasta que damos con un espacio vac\xc3\xado. Una vez la ronda terminada, nosotros balanceamos el arreglo insertando espacios entre cada elemento._NEWLINE_Siguiendo los tres pasos importantes del algoritmo:_NEWLINE_1. B\xc3\xbasqueda binaria:_NEWLINE_Encontrando la posici\xc3\xb3n de inserci\xc3\xb3n aplicando b\xc3\xbasqueda binaria dentro de los elementos ya insertados. Esto puede ser hecho movi\xc3\xa9ndose por las partes izquierda o derecha de forma recursiva y viendo si encontramos un espacio vac\xc3\xado en el medio._NEWLINE_2. Inserci\xc3\xb3n:_NEWLINE_Insertando el elemento en la posici\xc3\xb3n encontrada e intercambiando los elementos_NEWLINE_siguientes 1 por 1 hasta que choquemos con un espacio vac\xc3\xado._NEWLINE_3. Re-Equilibrando:_NEWLINE_Insertando espacios entre cada par de elementos en el arreglo. Esto toma tiempo lineal, y producto que hay log n rondas en el algoritmo, el re-equilibrio total toma_NEWLINE_O(n logn).\n_START_SECTION_\nPseudoc\xc3\xb3digo\n_START_PARAGRAPH_\nproc rebalance(A, begin, end)_NEWLINE_    r \xe2\x86\x90 end_NEWLINE_    w \xe2\x86\x90 end * 2_NEWLINE_    while r >= begin_NEWLINE_        A[w+1] \xe2\x86\x90 gap_NEWLINE_        A[w] \xe2\x86\x90 A[r]_NEWLINE_        r \xe2\x86\x90 r - 1_NEWLINE_        w \xe2\x86\x90 w - 2_NEWLINE_proc sort(A)_NEWLINE_    n \xe2\x86\x90 length(A)_NEWLINE_    S \xe2\x86\x90 new array of n gaps_NEWLINE_    for i \xe2\x86\x90 1 to floor(log2(n) + 1)_NEWLINE_        for j \xe2\x86\x90 2^i to 2^(i+1)_NEWLINE_            ins \xe2\x86\x90 binarysearch(A[j], S, 2^(i-1))_NEWLINE_            insert A[j] at S[ins]_NEWLINE_Aqu\xc3\xad, binarysearch(A, k) efectua b\xc3\xbasqueda binaria en los primeros k elementos de A de la ubicaci\xc3\xb3n donde se insertar\xc3\xa1 el elemento A[j], salt\xc3\xa1ndose los vac\xc3\xados. La inserci\xc3\xb3n tendr\xc3\xada que favorecer los vac\xc3\xados sobre los ocupados.'