Gnome sorting

The central idea is to walk to the line of pairs, to check them and if they are unordered then swap them. Otherwise - forward to the next pair (1 position forward, not 2, ie, from (1,2) to (2,3) in 1,2,3,4). But if we swapped the pair, we shift one pair backward and check them again. If it's impossible (we are already at the beginning), then shift forward to the pair next after tested one. The end is when no more pairs to test (tested - ok, forward - ops, we are at the end).

Why do we shift backward after the swap? Look at the pic:

5 3 . .
3 5 . .
    ^^^  test now this (no possible backward shift)
3 5 10 4 . .
3 5 4 10 . .
    ^^^^ swapped and now 4 is moved to back and
         4 is in the correct place relatively to 10
         but it may be in the wrong place relatively
         to prev. pair - and it's true (5, 4)! So,
         we must fix 4 relatively to it's prev. item
         BCS the next one is ok (10). After it we
         will continue our motion forward.

Why we shift forward to 1 position, not to 1 pair? I.e. from (1,2) to (2,3) in 1,2,3,4, but not from (1,2) to (3,4)! Because after a move fix, backward - the next move forward can hit again broken ordering (after swapping), and it wrong order may be in (2,3)-positions, not in the next whole pair.

def swap(arr, i, j):
    tmp = arr[i]
    arr[i] = arr[j]
    arr[j] = tmp
    

# array    in focus       actions
# -----------------------------------------------------------------------------------------
# 4 3 1 2   (4, 3)     not ok, swap, backward
# 3 4 1 2   (3, 4)     ok, forward
# 3 4 1 2   (4, 1)     not ok, swap, backward
# 3 1 4 2   (3, 1)     not ok, swap, backward (not possible, forward to next/not tested pair)
# 1 3 4 2   (4, 2)     not ok, swap, backward
# 1 3 2 4   (3, 2)     not ok, swap, backward
# 1 2 3 4   (1, 2)     ok, forward
# 1 2 3 4   (3, 4)     ok. forward (not possible - end)
def gnome_sort(arr):
    i = 1
    while i < len(arr):
        if arr[i - 1] > arr[i]:
            swap(arr, i - 1, i)
            if i == 1:
                i += 1
            else:
                i -= 1
        else:
            i += 1

a = [10, 2, 0, 8, 5, 7, 1, 2, 9, 6, 0, 60, 12, 34, 8, 6, 3, 1, 11]
gnome_sort(a)
print(a)