Gnome Sort

Gnome sort, also known as stupid sort, is a variation of insertion sort that does not use nested loops, building a sorted list one element at a time by moving each item to its correct position through a series of swaps. It was known for a long time and used without a formal name before being popularized by the Iranian computer scientist Hamid Sarbazi-Azad in 2000 and later described and named gnome sort by Dick Grune. Gnome sort performs at least as many comparisons as insertion sort and shares its asymptotic running time characteristics, with an average running time of O(n squared) that tends toward O(n) when the list is already nearly sorted.