The problem is that you can look at this and, after a few seconds, think you've formed an intuition on how it must work, but your intuition is wrong. It seems like the only way to really show how weird this is would be by creating an animation that shows how it shuffles entries around.

(Edit) I gave it a shot: https://jsfiddle.net/odwh6cL5/45/

I agree. At first I thought it was doing something very simple but I am not so sure anymore. When you check the condition for the swap, you realize it almost works counterproductively while i<j because it keeps pushing smaller numbers in the wrong direction, but then it starts "fixing" those mistakes when i>j. I don't find this intuitive at all.

>In Bubble Sort you only ever compare adjacent items. Here you don't.

This is the first thing I noticed and it pretty much says it all. It is not bubble sort because there are no bubbles bubbling to the top. Instead it compares every possible element pair combination.

The way I understood it, it's more similar to insertion sort, but you insert from the top instead of from the bottom of the already-sorted part.

> In that latter case I'd really appreciate a better explanation for what you think is going on, and why you think this is "just an unoptimised Bubble Sort".

I can try to explain that. The algorithm really is doing a bubble sort, with some unnecessary extra work added. It also does a bit of necessary extra work.

Here is the useful work done by the algorithm:

1. First, preprocess the list so that the maximal element occurs first. (It's a 1-indexed list, so position 1 holds the highest element of the list.)

2. Now, we consider an invariant: the part of the list up to (and including) the maximal element is always sorted. Right now that consists of indices 1-1, and since that range contains only one value it's necessarily sorted. We will use a variable ("i") to remember where the maximal element is.

3. Now, the outer loop: we start at the index immediately after the maximal element, index i+1. Whatever value is in there, we bubble it to the left (this is the inner loop), in the manner of a standard bubble sort: we compare it to index i, and if it's lower (which is always, since i holds the maximal element), we swap. Then we compare index i to index i-1, and so on. Once we find an element that is smaller than the one we've been bubbling to the left, we stop, and our invariant is restored: the list up to the maximal element is still sorted. But the space covered by the invariant has increased by one slot. We increment i.

4. The loop continues until i points to the last slot in the list, at which point we're done. The invariant tells us the the list up to i is sorted, and since i points to the last value in the list, the whole list is sorted.

-----

The algorithm I've described sends i forward from the beginning to the end of the list and j backwards from i+1 to the beginning of the list. The algorithm in the paper does all the same work, but it also does more work, instead having j cross the entire list every time. (It also sends j forwards, like i, but this doesn't matter.†) The only reason for this is to make the algorithm simpler to write down. This is why it's "unoptimized bubble sort". Note that, in the algorithm of the paper, once the maximum value has been swapped into i, the check A[i] < A[j] can never succeed, but we ignore that and keep advancing j instead of just terminating the j loop. This looks especially stupid because the maximal value will always occur before i (except when i = 1, which is the stage that, in my algorithm, is called "preprocessing").

In a bubble sort, if your cursor is at 5, and you want to move A[6] to index 3, you need to make 3 swaps and 3 comparisons. In the paper's sort, when your cursor is at 5 and you want to move A[6] to index 3, you need to make 3 swaps and n comparisons, where n is the length of the full list.

-----

If you're interested in why the j loop is the same thing as a bubble sort, here's an expansion on the example above:

We're in the process of bubble sorting [1 4 8 11 24 5], looking at the 5. Because 5 is more than 4 but less than 8, we want it to ultimately end up at index 3. Everything else will shift up by one index to accommodate this.

In a bubble sort, we swap the 5 down into index 5, then we swap the 5 down into index 4, and then we swap it down into index 3.

    swap(&a6, &a5);
    swap(&a5, &a4);
    swap(&a4, &a3);

In the paper's sort, we do exactly the same thing from the other direction:

    int* temp;
    *temp = a6;      /* we want to put this into its correct position */
    swap(&a3, temp); /* done, but we need to remember what was in a3 so we can swap it up to a4 */
    swap(&a4, temp); /* done, but now we need to remember what was in a4 so we can swap it up to a5 */
    swap(&a5, temp); /* take a guess... */
    swap(&a6, temp);

but there's a slight optimization where instead of using a temporary variable to hold the values we're swapping, we just use the space after the maximal element (which makes `swap(&a6, temp)` redundant - after the optimization, those are the same address).

† It matters a little bit - a bubble sort is free to terminate the inner loop as soon as the value being bubbled has found its correct position. But in the paper's algorithm, we have to find the correct position first, which is done by scanning every index that contains a lower value until we eventually find the first one that doesn't. That work is optimized out of a bubble sort. However, since the paper's sort is committed to scanning the entire list in the inner loop anyway, the fact that the order of bubbling is wrong doesn't require any more extra scanning beyond what they've already committed to.

I used to teach this to beginners all the time. I called it "exchange sort", though I'm not sure where I ever got that name from.

Beginners to sorting are often still somewhat struggling with for loops (especially the three-part C kind), struggling with indexing an array, struggling with swaps. It's overwhelming.

This is kind-of like pseudocode for a simple sort -- it has the same rough outline, but no tricky bits. It allows them to get their brains around the basic algorithm, and only after that you trace through an execution on the board to show them that it wastes a lot of time moving things around.

Then you can show them insertion sort as an optimization, and from that move on to fancier ones.

This isn't surprising to me in the least that it works.

In the first pass (i=1), A[1] will end up with the largest value and a later pass cannot displace it.

In the second pass (i=2), A[2] will end up with the 2nd largest value (which might be the same as the largest value, if it appeared more than once in the list). And so on.

Isn't that just BubbleSort?

And, if so: they're writing Arxiv papers on BubbleSort now?

    A[i] < A[j]

Thanks! Macroexpanded:

Is this the simplest (and most surprising) sorting algorithm? - https://news.ycombinator.com/item?id=28758106 - Oct 2021 (318 comments)

The “royal we” is common for single author academic work. I’m honestly unsure why. StackExchange seems to think it refers to both author and reader together. I think it conveys a sort of distance from the author, giving the writing less of a personal and more general tone.

https://hsm.stackexchange.com/questions/2002/how-did-royal-w...

This is formal academic style, not wolfram style.

This intrigues me.

Would you be willing ... without looking at this article ... to provide exactly the code you "use all the time"?

I'd like to compare what you write with the code in the article, because code that I write as a quick and dirty sort is definitely not this.

In particular, this seems to take items that are already the right way round, and swaps them. I definitely don't do that. To be specific, I just knocked this out:

    #!/usr/bin/python
    a = [ 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9 ]
    N = len(a)

    for i in range(0,N-2):
        for j in range(i+1,N-1):
            if a[i]>a[j]:
                a[i],a[j] = a[j],a[i]

    print a

Specifically, note that I ask if a[i] is bigger than a[j] and if so then I swap them. The code in the article appears to do exactly the wrong thing, and I'd be surprised if your "go to" code does it the same way as the code in the article.