Foundations · Beginner
Gnome Sort
Walk forward while neighbors are ordered; swap and step backward when they are not.
- Best
- O(n)
- Average
- O(n²)
- Worst
- O(n²)
- Space
- O(1)
- Stability
- Stable
- Memory model
- In-place
How it builds order
- Compare the current item with its left neighbor.
- Move forward when they are ordered.
- Otherwise swap and move backward.
- Finish when the walker reaches the right edge.
Why it works
Stepping backward repairs any new inversion created to the left; reaching the right edge means every adjacent pair is ordered.
Watch for: The walker revisits the prefix until the new value has bubbled into place.
The interactive version of this page adds the full trace, synchronized pseudocode, practice decisions, input experiments, and mastery review.