Gnome sort is a sort algorithm which is similar to insertion sort except that moving an element to its proper place is accomplished by a series of swaps, as in bubble sort. The name comes from the supposed behavior of the Dutch garden gnome in sorting a line of flowerpots. It is conceptually simple, requiring no nested loops. The running time is O(n2), and the constant has been reported to be slightly higher than Bubble sort (although this would depend on the details of the architecture and the implementation). Python code follows:
def GnomeSort(l):
i = 0
while (i < len(l)):
if i == 0 or l[i - 1] <= l[i]:
i += 1
else:
l[i], l[i - 1] = l[i - 1], l[i]
i -= 1
return l