Gnome Sort

Gnome sort maintains a sorted prefix with one index. If a[i-1] <= a[i], the index advances. If the pair is inverted, the values swap and the index steps back so the displaced value can continue moving toward its insertion point. Reaching index 0 immediately resumes at 1.

The mechanism is Insertion Sort expressed through adjacent swaps rather than shifting a saved value. Each swap removes one inversion, so the process terminates. Strict comparison keeps equal values from crossing, making the sort stable.

VisualizationVisualizationComplexityComplexity

Visualization

Forward steps confirm the current prefix remains ordered. A swap steps back by one position; repeated swaps walk the smaller value left until its predecessor is no greater, after which the scan moves forward again.

Complexity

n

number of elements in the array

TimeSpace

• Best
• Average
• Worst

Boundary and implementation

Ordered input needs one forward scan, but reverse-ordered input contains n(n-1)/2 inversions and forces that many adjacent swaps. Insertion Sort reaches the same asymptotic bound with fewer writes because it shifts a block and writes the inserted value once; Gnome Sort is mainly useful for seeing inversion removal in a single loop.

C# implementation

public static void GnomeSort(int[] values)
{
    var i = 1;
    while (i < values.Length)
    {
        if (values[i - 1] <= values[i])
        {
            i++;
        }
        else
        {
            (values[i - 1], values[i]) = (values[i], values[i - 1]);
            i = Math.Max(1, i - 1);
        }
    }
}

Clamping the index to 1 avoids reading values[-1] after a swap at the front.

Questions

What guarantees termination?

Every swap removes one adjacent inversion, and a forward step eventually passes an ordered pair. The finite inversion count cannot decrease forever.

Why can Insertion Sort perform fewer writes with the same asymptotic time?

Gnome Sort swaps through every crossed neighbor. Insertion Sort can save the moving value, shift the larger block, and write the saved value once.

References

• Dick Grune, “Gnome Sort — The Simplest Sort Algorithm” — the algorithm author’s primary description and compact implementation.
• NIST Dictionary of Algorithms and Data Structures: gnome sort — authoritative definition, classification, and historical notes.