How to implement Gnome sort in C++

Gnome sort is a variation of insertion sort, which performs sorting without any nested loops. It was first called a Stupid sort, but later, it was named Gnome sort.

Note: The algorithm of gnome sort is inspired by a Dutch garden Gnome’s sorting technique, where they sort the flowerpots by comparing two consecutive flowerpots. If the flowerpots are in order, they move forward; otherwise, they swap them backward.

The basic idea of this algorithm for sorting is to swap adjacent elements if they are not in order until the element is adjusted to its left sub-array. The sorting loop progresses if the adjacent elements are in order and move backward otherwise.

Let’s visualize the working of the gnome sort:

canvasAnimation-image
1 of 41

Algorithm

Let’s discuss the steps of the algorithm:

index := 1
while index < size(array)
    if index == 0 or array[index] >= array[index - 1]
        index := index + 1
    else
        swap array[index] and array[index - 1]
        index := index -1
Pseudo-code of the Gnome sort algorithm

Code

Let’s implement the code of Gnome sort in the following playground:

#include <iostream>
using namespace std;
void gnome_sort(int arr[], int n){
    int index = 1;
    while(index < n){
        if(index == 0 || arr[index] >= arr[index - 1]){
            index++;
        }
        else{
            std::swap(arr[index], arr[index-1]);
            index--;
        }
    }
}
int main() {
    int arr[] = {15, 13, 24, 7, 18, 3, 22, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    std::cout << "Original Array: ";
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }
    gnome_sort(arr, n);
    std::cout << "\nSorted Array: ";
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }
    return 0;
}

Explanation

Let’s discuss the code below:

  • Line 5: We created a variable index to store the current index. We initialized it with a value 11.
  • Line 7: We use a while loop on index to perform sorting. This loop will iterate until the value of index is less than the array’s length.
  • Lines 8–14: We use the if-else condition to implement the algorithm’s logic. We increment the value of index if the value of the index is zero or the array elements at index and index-1 are in order. Otherwise, the elements are swapped, and the value of index is decreased.
  • Lines 19–24: We create an array and print it before sorting.
  • Lines 26–30: We call the gnome_sort() function and print the array after sorting.

Complexity

The time complexity of the Gnome sort algorithm is as follows:

  1. Best-case: The best-case time complexity of the Gnome sort is O(n)O(n).
  2. Worst-case: The worst-case time complexity of the Gnome sort is O(n2)O(n^2).
  3. Average-case: The average-case time complexity of the Gnome sort is O(n2)O(n^2).

The Gnome sort performs the in-place sorting and requires no extra space. So, the space complexity of the Gnome sort is O(1)O(1).

Benefits

  • The Gnome sort algorithm is simple and easy to implement.
  • It is a space-efficient algorithm because it requires no extra space to sort.
  • It is a stable sorting algorithm that maintains the order of equal elements.
  • It is an adaptive sorting algorithm that performs better on partially or nearly sorted lists.

Limitations

  • The worst-case time complexity of Gnome sort is O(n2)O(n^2), which means it can be slow for large arrays.
  • Its performance is very unpredictable, especially on larger datasets. It performs decently on some inputs and becomes extremely slow on others.
  • The Gnome sort is rarely used in practice due to its poor performance compared to other efficient sorting algorithms, such as merge sort, heap sort, quick sort, etc.

How to optimize the Gnome sort

We can optimize the performance of Gnome sort by doing some tweaks to its algorithm. These changes include the following:

  • Before performing the swapping steps, store the value of the index in a temporary variable and restore it after the element is placed into its location by swapping. This can save unnecessary variable increment steps.
  • Instead of comparing and swapping the element to the left subarray, we can use binary search to find the position of the element and shift elements. We can save comparisons by performing this step. It can be very useful where the comparison cost is high.

Unlock your potential: Sorting algorithms series – all in one place!

To continue your exploration of sorting algorithms, check out our series of Answers below:

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved