Gnome Sort

function gnomeSort(arr) {
    let i = 0;

    while (i < arr.length) {
        // If at beginning or current element is larger than previous
        if (i === 0 || arr[i] >= arr[i - 1]) {
            i++; // Move to next element (gnome takes a step forward)
        } else {
            // Current element is smaller than previous
            // Swap elements (gnome swaps pots)
            [arr[i], arr[i - 1]] = [arr[i - 1], arr[i]];
            i--; // Move back to check previous elements

            // If we've moved back to the beginning, take a step forward
            if (i === 0) {
                i++;
            }
        }
    }

    return arr;
}

How Gnome Sort Works

Gnome Sort is inspired by the way a garden gnome might sort flower pots. The gnome walks through the garden, comparing adjacent pots and swapping them if they're in the wrong order. When it finds a pot that's out of order, it swaps it and walks back to check previous pots.

Gnome's Garden Algorithm:

1. Start at beginning: Gnome starts at the first flower pot
2. Compare adjacent pots: Look at current pot and next pot
3. If in order: Take a step forward (move to next pot)
4. If out of order: Swap pots and step backward
5. Continue checking: Keep walking back until order is restored
6. Resume forward: Once fixed, continue moving forward

Key Characteristics:

• Stable: Maintains relative order of equal elements
• In-place: Requires only constant extra space O(1)
• Adaptive: Very efficient on nearly sorted arrays
• Simple: Easy to understand and implement
• Intuitive: Based on natural sorting behavior

Gnome's Movement Pattern:

• Forward movement: When elements are in correct order
• Backward movement: When out-of-order element is found
• Systematic checking: Ensures all previous elements are correct
• Gradual progress: Like insertion sort but with gnome-like steps

Performance Insights:

• Best Case: O(n) when array is already sorted
• Worst Case: O(n²) when array is reverse sorted
• Adaptive: Performance improves with partially sorted data
• Comparison count: Similar to insertion sort

Educational Value:

• Visual learning: Easy to visualize the gnome's movement
• Algorithm intuition: Demonstrates natural sorting behavior
• Step-by-step analysis: Clear cause-and-effect relationships
• Historical interest: Shows creative algorithm design inspiration

Comparison with Insertion Sort:

• Similar approach: Both build sorted array incrementally
• Different movement: Gnome sort moves back on every out-of-order element
• Same complexity: O(n²) worst case, O(n) best case
• Educational focus: Gnome sort emphasizes the back-and-forth nature