python - What is this odd sorting algorithm?

Question

Some answer originally had this sorting algorithm:

for i from 0 to n-1:
    for j from 0 to n-1:
        if A[j] > A[i]:
            swap A[i] and A[j]

Note that both i and j go the full range and thus j can be both larger and smaller than i, so it can make pairs both correct and wrong order (and it actually does do both!). I thought that's a mistake (and the author later called it that) and that this would jumble the array, but it does appear to sort correctly. It's not obvious why, though. But the code simplicity (going full ranges, and no +1 as in bubble sort) makes it interesting.

Is it correct? If so, why does it work? And does it have a name?

Python implementation with testing:

from random import shuffle

for _ in range(3):
    n = 20
    A = list(range(n))
    shuffle(A)
    print('before:', A)

    for i in range(n):
        for j in range(n):
            if A[j] > A[i]:
                A[i], A[j] = A[j], A[i]

    print('after: ', A, '
')

Sample output (Try it online!):

before: [9, 14, 8, 12, 16, 19, 2, 1, 10, 11, 18, 4, 15, 3, 6, 17, 7, 0, 5, 13]
after:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 

before: [5, 1, 18, 10, 19, 14, 17, 7, 12, 16, 2, 0, 6, 8, 9, 11, 4, 3, 15, 13]
after:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 

before: [11, 15, 7, 14, 0, 2, 9, 4, 13, 17, 8, 10, 1, 12, 6, 16, 18, 3, 5, 19]
after:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 

Edit: Someone pointed out a very nice brand new paper about this algorithm. Just to clarify: We're unrelated, it's a coincidence. As far as I can tell it was submitted to arXiv before that answer that sparked my question and published by arXiv after my question.

Answer 1

It's a correct but odd and inefficient insertion sort.

Let's first visualize it by printing A after each complete inner loop iteration. Example:

before: [1, 12, 13, 8, 15, 18, 19, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [19, 1, 12, 8, 13, 15, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 19, 12, 8, 13, 15, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 12, 19, 8, 13, 15, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 8, 12, 19, 13, 15, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 8, 12, 13, 19, 15, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 8, 12, 13, 15, 19, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 8, 12, 13, 15, 18, 19, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 8, 12, 13, 15, 16, 18, 19, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 7, 8, 12, 13, 15, 16, 18, 19, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 7, 8, 11, 12, 13, 15, 16, 18, 19, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 6, 7, 8, 11, 12, 13, 15, 16, 18, 19, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 6, 7, 8, 11, 12, 13, 14, 15, 16, 18, 19, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 3, 6, 7, 8, 11, 12, 13, 14, 15, 16, 18, 19, 2, 9, 5, 4, 0, 10, 17]
        [1, 2, 3, 6, 7, 8, 11, 12, 13, 14, 15, 16, 18, 19, 9, 5, 4, 0, 10, 17]
        [1, 2, 3, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 18, 19, 5, 4, 0, 10, 17]
        [1, 2, 3, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 18, 19, 4, 0, 10, 17]
        [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 18, 19, 0, 10, 17]
        [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 18, 19, 10, 17]
        [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 17]
        [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
after:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 

Graphically, but updating after every swap, the red bar shows index i (code here):

For i = 0, it actually does more or less jumble the list, but it brings the largest value to A[0] (or one largest value, if there are multiple). From then on, this value will act as a sentinel.

Due to this initial jumbling, it would be hard (and pointless) to state an invariant based on the initial state of the array. Instead, let's define A0 to be the state of the array after the outer loop for i = 0:

Invariant: After the outer loop for some i:

• The overall largest value is at A[i]
• A[0 to i] contain A0[0 to i] in sorted order.

Proof by induction:

Base case i = 0 is trivial.

Cases i > 0: Before the outer loop with this i, we have the sentinel (overall largest value) at A[i-1], and A[0 to i-1] contains A0[0 to i-1] in sorted order. Now the inner loop goes over all elements and we swap A[i] and A[j] whenever A[j] > A[i]. Let's look at an example row from above again:

[1, 7, 8, 12, 13, 15, 16, 18, 19, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]

The 19 is the sentinel, the part up to it is sorted, and i is the index of the 11. What happens when we go with j from 0 to the end? The values 1, 7 and 8 are not larger than the 11, so nothing happens. The 12 is larger, so it'll get swapped with the 11:

[1, 7, 8, 11, 13, 15, 16, 18, 19, 12, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]

Now it's the 12 that's at index i. And next it gets compared to 13. Since 13 is larger, they're swapped:

[1, 7, 8, 11, 12, 15, 16, 18, 19, 13, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]

This continues, always swapping, until we swap with the sentinel:

[1, 7, 8, 11, 12, 13, 16, 18, 19, 15, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
[1, 7, 8, 11, 12, 13, 15, 18, 19, 16, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
[1, 7, 8, 11, 12, 13, 15, 16, 19, 18, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
[1, 7, 8, 11, 12, 13, 15, 16, 18, 19, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]

At this point the insertion of the 11 into the sorted portion is complete. And the sentinel moved to index i, where it then prevents any further swaps during the inner loop (i.e., swaps of it with elements further right). In general, for a new value (like the 11), the numbers smaller than it stay where they are, and the numbers larger than it are swapped out and back in one place to the right.

When we're all done, we've had the outer loop with i = n-1. The invariant then tells us that A[0 to n-1] contain A0[0 to n-1] in sorted order. I.e., the array indeed ends up correctly sorted.

Why I call it an insertion sort: After the jumbling i = 0, if you look at the array after every full inner loop, it's indistinguishable from insertion sort (see my big visualization block at the top). For example, the 11 simply got inserted into the sorted part on its left. It just differs by how that insertion happens. Normal insertion sort "bubbles" the 11 leftwards until its correct place, not even looking at the even smaller numbers. This algorithm here instead searches the insertion point, starting from the very left, and then inserts the 11 there and "bubbles" the larger numbers up to the sentinel rightwards. And then continues with fruitless further comparisons against the sentinel now sitting at A[i].

Update: smusamashah shared their fantastic visualization tool, which nicely lets us compare this algorithm with the other algorithms that this was claimed to be. Click the checkmarks on the right for Bubble Sort, Insertion Sort and Selection Sort, then click Start. You'll again see our sort is very much like insertion sort, and not at all like the others. And if you instead do Exchange Sort (sadly not included) you'll see that's more like Selection Sort (but slower because it swaps more and the tool shows all swaps).