Size:15

Overview & Concept

Gnome Sort (originally proposed by Hamid Sarbazi-Azad as Stupid Sort and renamed by Dick Grune) is an elementary in-place sorting algorithm inspired by a garden gnome inspecting a line of flower pots: if the current pot is in order with the previous one, the gnome steps forward; if not, the gnome swaps them and steps backward.

How It Works

Single Index Pointer: Operates with a single pointer pos starting at index 0.

Forward Step on Order: If pos == 0 or A[pos] >= A[pos - 1], advances pos by 1.

Backward Step on Inversion: If A[pos] < A[pos - 1], swaps the pair and decrements pos by 1.

Conceptual Equivalence: Functions analogously to Insertion Sort, but moves elements using repeated adjacent swaps instead of shifting.

Step-by-Step Execution

1. Position CheckIf pos == 0, advance pos to 1.

2. Order InspectionCompare A[pos] with A[pos - 1].

3. Forward or Backward StepIf ordered, pos++. If inverted, swap A[pos] and A[pos - 1], then pos--.

4. TerminationComplete when pos reaches array length n.

Asymptotic Complexity Analysis

Metric	Best Case	Average Case	Worst Case	Space Complexity
Complexity Bound	O(n)	O(n²)	O(n²)	O(1)
Explanation	Optimal input arrangement minimizing operations.	Expected time for uniformly distributed randomized inputs.	Adversarial degenerate conditions requiring full traversal.	Auxiliary memory allocated beyond original input size.

Pseudocode & Invariants

Algorithm Logic

procedure gnomeSort(A):
  pos = 0
  while pos < length(A):
    if pos == 0 or A[pos] >= A[pos - 1]:
      pos = pos + 1
    else:
      swap(A[pos], A[pos - 1])
      pos = pos - 1
  return A

Algorithmic Invariants

Prefix Verification: The sub-array A[0..pos-1] has been verified to be sorted whenever the gnome steps forward.

Correctness Guarantee: Invariants hold true prior to loop entry, are preserved during every iteration, and guarantee correct post-condition upon termination.

Advantages & Disadvantages

Key Advantages

•Extremely simple code with no nested loops required.
•In-place sorting with O(1) auxiliary memory.
•Stable sorting behavior.
•O(n) best-case time on already-sorted arrays.

Trade-offs & Limitations

•O(n²) average and worst-case time complexity.
•High number of swap operations compared to standard Insertion Sort.

Real-World Applications

Embedded Tiny Microcontrollers

Micro-controllers with ultra-constrained code memory (sub-kilobyte ROM).

Decision Guide: When to Use

Ideal Scenarios

✓When code size must be minimized to absolute bare minimum instructions.
✓When data is already sorted or nearly sorted.

Consider Alternatives When

✕When sorting large datasets.

Compare trade-offs and complexity across complementary tools in AlgoViz.

Insertion Sort Bubble Sort Cocktail Shaker Sort