Gnome sort

El algoritmo de ordenación conocido como gNome_sort tiene una historia de invención cuasi paralela. Durante un tiempo existió la polémica sobre su invención, finalmente atribuida a Hamid Sarbazi-Azad quien lo desarrolló en el año 2000 y al que llamó Stupid sort (Ordenamiento estúpido). Cuando Dick Grune lo inventó (más apropiadamente, lo reinventó) y documentó,​ no halló evidencias de que existiera y en palabras suyas, dijo de él "the simplest sort algorithm"​ (es el algoritmo más simple) y quizás tenga razón, pues lo describió en sólo cuatro líneas de código. Dick Grune se basó en los gnomos de jardín holandés y la manera en que se colocan dentro de los maceteros (ver la referencia anterior) y de ahí también el nombre que le dio. Netamente es un algoritmo de burbuja con una clara particularidad: recorre el array a ordenar como una cremallera, en un vaivén, o bien puede ser definido como un ordenamiento de burbuja bidireccional, que a su vez son llamados también cocktail shaker (agitador de cócteles), por la forma en que trabaja... Cumple estrictamente hablando con la complejidad O(n²).