Gnome Sort

Gnome sort maintains a sorted prefix with a single index. An ordered pair, a[i-1] <= a[i], moves the index forward. An inverted pair swaps, then the index steps back so the displaced value can keep moving toward its insertion point. At the front of the array, the scan resumes from index 1.

The mechanism is Insertion Sort expressed as adjacent swaps instead of shifting a saved value. Every swap removes one inversion, which guarantees termination. Equal values never cross because the comparison is strict, so the sort is 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

TimeSpace

• Best: O(n)
• Worst/Average: O(n²)

n

number of elements in the array

Inversion cost and adjacent swaps

Ordered input needs one forward scan. Reverse-ordered input contains n(n-1)/2 inversions and forces the same number of adjacent swaps. Insertion Sort has the same asymptotic bound but writes less: it shifts a block and places the saved value once. Gnome Sort is mainly useful as a compact demonstration of inversion removal.

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.

References

• Dick Grune, “Gnome Sort — The Simplest Sort Algorithm”