> 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".

> 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.