Gnome Sort

Walks forward comparing adjacent pairs; when it finds one out of order it swaps and steps back, otherwise it steps forward — like a garden gnome sorting flower pots. Conceptually it is insertion sort with a single index and no nested loop.

Best

O(n)

Average

O(n²)

Worst

O(n²)

Space

O(1)

Stable

Yes