Overview
Gnome Sort is a simple sorting algorithm similar to the insertion sort, but it
operates with a concept similar to the way a garden gnome sorts flower pots.
The algorithm works by comparing the current element with the previous one and
swapping them if they are out of order. It then moves one step backward and
repeats the process. If the elements are in order, it moves one step forward.
The process continues until the entire list is sorted.
Time Complexity:
Best case: O(n) - When the list is already sorted or nearly sorted
Average case: O(n²) - As the gnome has to backtrack frequently, similar to insertion sort
Worst case: O(n²) - When the array is initially in reverse order, requiring maximum
backtracking
Space Complexity: O(1) - It is an in-place sorting algorithm.
i = 1while i < length(list) if i == 0 or list[i - 1] ≤ list[i] i += 1 else swap(list[i], list[i - 1]) i -= 1SHORT EXPLANATION------------------1. Start at the first element (index 1) of the list2. If the current element is in the correct order relative to the previous element, move forward3. If the current element is smaller, swap it with the previous one - Then move one step back to compare the swapped element again4. Continue this process until you reach the end of the list5. The algorithm ensures that smaller elements move toward the beginning and larger ones toward the end, similar to the way a gnome sorts flower pots