Gnome Sort

Gnome sort is a simple comparison-based sorting algorithm. It scans forward through the array, and when it finds two adjacent elements out of order, it swaps them and steps backward. When elements are in order, it moves forward.

The behavior resembles insertion sort, but instead of shifting elements, it repeatedly swaps while moving backward.

Problem

Given a sequence $A$ of length $n$ , reorder it such that

A[0] \le A[1] \le \cdots \le A[n-1]

Algorithm

Maintain an index that moves forward when order is correct and backward after swaps.

gnome_sort(A):
    i = 0
    n = length(A)

    while i < n:
        if i == 0 or A[i - 1] <= A[i]:
            i = i + 1
        else:
            swap(A[i], A[i - 1])
            i = i - 1

Example

Let

A = [5, 3, 2, 4]

Steps:

step	index	action	result
1	1	swap (5,3)	[3,5,2,4]
2	1	keep	[3,5,2,4]
3	2	swap (5,2)	[3,2,5,4]
4	1	swap (3,2)	[2,3,5,4]
5	2	keep	[2,3,5,4]
6	3	swap (5,4)	[2,3,4,5]

Sorted result:

[2,3,4,5]

Correctness

At each step, the algorithm ensures that the prefix up to index $i$ is locally ordered. When a violation occurs, swapping and stepping backward fixes the inversion. This process continues until all adjacent pairs are in order, which implies global sorted order.

Complexity

case	comparisons	time
best	$n$	$O(n)$
worst	$O(n^2)$	$O(n^2)$
average	$O(n^2)$	$O(n^2)$

Space complexity:

O(1)

Properties

stable
in-place
conceptually simple

When to Use

Gnome sort is mainly useful for educational purposes. It demonstrates how local swaps can simulate insertion behavior. In practice, insertion sort is more efficient due to fewer swaps.

Implementation

def gnome_sort(a):
    i = 0
    n = len(a)

    while i < n:
        if i == 0 or a[i - 1] <= a[i]:
            i += 1
        else:
            a[i], a[i - 1] = a[i - 1], a[i]
            i -= 1

    return a

func GnomeSort[T constraints.Ordered](a []T) {
    i := 0
    n := len(a)

    for i < n {
        if i == 0 || a[i-1] <= a[i] {
            i++
        } else {
            a[i], a[i-1] = a[i-1], a[i]
            i--
        }
    }
}