El algoritmo de ordenación MÁS EFICIENTE posible

Hacía tiempo que se conocía el peor algoritmo de ordenación posible y su coste, pero no se sabía cual podría ser ni el coste, ni mucho menos cómo podría ser el mejor algoritmo para ordenar (no mezclar, sin más consumo de memoria que la propia lista)


Un concienzudo estúdio teórico ha desvelado la respuesta a este problema nada trivial y ahora...
Ya se conoce el coste del mejor algoritmo de ordenación posible, y no sólo eso YA SE CONOCE EL MEJOR ALGORITMO DE ORDENACIÓN POSIBLE

Esto puede parecer trivial, pero es realmente un problema teórico enorme
No es el qsort ni variantes semejantes, es muchísimo mejor y revolucionario


El coste es O(n) pero todavía es teórico, no se ha conseguido llevar a la práctica

Hay varias universidades tratando de hacerlo efectivo

Consta de dos pasos muy sencillos de entender, pero el segundo paso, no ha sido resuelto

Es curioso porque está inspirado en el peor algoritmo de ordenación posible (que sí se conocía desde hace mucho tiempo)


Disfruta de esta revelación todavía poco popular, sé privilegiado...

bogo-sort: /boh`goh·sort´/, n.

(var.: stupid-sort) The archetypical perversely awful algorithm (as opposed to bubble sort, which is merely the generic bad algorithm). Bogo-sort is equivalent to repeatedly throwing a deck of cards in the air, picking them up at random, and then testing whether they are in order. It serves as a sort of canonical example of awfulness. Looking at a program and seeing a dumb algorithm, one might say “Oh, I see, this program uses bogo-sort.” Esp. appropriate for algorithms with factorial or super-exponential running time in the average case and probabilistically infinite worst-case running time. Compare bogus, brute force.

A spectacular variant of bogo-sort has been proposed which has the interesting property that, if the Many Worlds interpretation of quantum mechanics is true, it can sort an arbitrarily large array in linear time. (In the Many-Worlds model, the result of any quantum action is to split the universe-before into a sheaf of universes-after, one for each possible way the state vector can collapse; in any one of the universes-after the result appears random.) The steps are: 1. Permute the array randomly using a quantum process, 2. If the array is not sorted, destroy the universe (checking that the list is sorted requires O(n) time). Implementation of step 2 is left as an exercise for the reader.

http://www.catb.org/~esr/jargon/html/B/bogo-sort.html