Gnome Sort

Gnome Sort is a sorting algorithm that emulates the movement of a Turing machine – having the pointer only be able to move one step at a time.
How Gnome Sort works
Gnome Sort is a variation of Insertion Sort, but with the limitation of not being able to shift the pointer more than one step at a time. This make the visualisation look like there is a gnome moving back and forth along the array carrying over one item at a time.
Example
The array starts with the leftmost item being considered a ‘sorted’ sub-array of size 1. The second item is then picked up and moved leftward until it finds its correct position within the sorted subarray. At this point, Gnome Sort is identical to Insertion sort.
Once this is done, the elements are compared rightwards until an element is found that is out of order. This will eventually put the pointer at the next unsorted element at which point we can repeat the cycle.
The entire list is sorted when the rightward crawl overcomes the length of the array.
Visualisation
TBD
Time complexity
Gnome Sort uses comparisons and swaps to sort the array
Comparisons
The time complexity for comparisons is n2/2, which makes sense since each step takes twice as long as Insertion Sort.
Swaps

Swaps are on the same order as well but half as much, n2/4.This is because when the gnome move right, no swaps are taking place.
Distribution
This is how the comparisons and swaps are distributed for this sorting algorithm of size 100 for 1,000,000 sorts.
These distributions aren’t anything out of the ordinary. Just two normal distributions.
C code
void gnome_sort(int *p, int len) {
int i = 1;
while (i < len) {
if (i == 0) {
// Reached left end, move right and skip
i++;
continue;
} else if (is_greater_than_p(&p[i-1], &p[i]) && i != len) {
// Swap pots and move leftwards
swap(&p[i], &p[i-1]);
i--;
} else {
// Move rightwards
i++;
}
}
}