Summary

Gnome Sort is an interesting variation of Insertion Sort that achieves its goal without any nested loops. The algorithm is named after a story of a garden gnome sorting a line of flower pots. The gnome's position in the array moves forward when elements are in order, but when it finds an out-of-place element, it swaps it with the previous one and moves backward, carrying the element to its correct sorted position. This back-and-forth movement continues until the gnome reaches the end of the array.

How it Works

• Start with the "gnome" at the beginning of the array (position pos = 0).

• The gnome compares the element at its current position with the element to its left (pos and pos-1).

• If the gnome is at the very beginning, or if the current element is greater than or equal to the previous one, they are in the correct order. The gnome steps one position forward.

• Else, the elements are out of order. The gnome swaps them and steps one position backward.

• Repeat this process until the gnome has moved past the end of the array. At this point, the array is fully sorted.