# Gnome Sort

# 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.

```id="n8k3x1"
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

```id="v6m2q9"
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
```

```id="r3k8z4"
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--
        }
    }
}
```