Bead Sort: Ordenamiento en O(sqrt(n))

According to Dijkstra, “our systems are much more complicated than can be considered healty, and are too messy and chaotic to be used in comfort and confidence. …unmastered complexity is at the root of the misery”

Considérese un conjunto A de n enteros positivos a ordenar y asúmase que el número más grande en A es m. Entonces, el ábaco debe tener al menos m varillas y n niveles. El algoritmo Bead Sort es el siguiente:

Para todo a en A déjense caer a cuentas (una cuenta por varilla) a lo largo de las varillas, iniciando de la primera varilla hasta la a-ésima. Finalmente, las cuentas, vistas nivel por nivel, representan A en orden ascendente.

¿Cómo se puede implementar este algoritmo en tiempo O(sqrt(n))? No es posible en una computadora binaria finita convencional. Sin embargo, es posible lograrlo construyendo físicamente el ábaco y empleando la gravedad para dejar caer las cuentas; el tiempo que tarda una cuenta en caer es del tipo t² = αd/g, y se puede paralelizar.

Si fuera físicamente posible mover todas las cuentas instantáneamente y al mismo tiempo (ignorar la existencia del tiempo) el algoritmo tendría, naturalmente, tiempo O(1). La implementación en hardware tiene tiempo O(n) y, en software, O(S) donde S es la suma de los enteros en la entrada.

Artículo, con implementaciones para O(n) (enlace a html que enlaza a PDF): Bead–Sort: A Natural Sorting Algorithm