The low-indexed portion is sorted, but isn't guaranteed to contain the lowest or the highest i elements of the list (except when i=1), and the list is ultimately sorted in decreasing, not increasing order. The final sort doesn't occur until the last iteration of the outer loop when the inequality is reversed (the interesting variable, j, is on the right).

Because of that, the proof outline discussed here doesn't work.

Consider what happens if the unique smallest element starts at position n. It is placed at the start of the list (the correct final position) in the final iteration of the outer loop (i=n), and not before.

Proof (for simplicity the list is indexed 1 to n):

Let A[n] < A[k] for all k != n in the initial list.

Elements are only swapped when A[i] < A[j]. If i != n and j = n, then A[i] > A[n] = A[j], so A[n] is not swapped.

Then, when i = n and j = 1, A[i] = A[n] < A[1] = A[j], so A[1] and A[n] are swapped, placing the smallest element in position 1 at last.

Solution is even simpler:

Empty case after 1 iteration (I=1) the largest number is at position 1 Base case: after 2 iterations (I=2) the 2 first elements are ordered, and the largest number is at position 2

Assume N case: after N iterations the first N numbers are ordered (within the sub list, not for the entire array) and the largest number is at position N

N+1 case (I=N+1): For Every J<N+1 and A[J]>= A[I] nothing will happen From the first J where J<N+1 and A[J] < A[I] (denote x) each cell will switch as A[J] < A[J+1] At J=N+1 the largest number will move from A[N] to A[I] For every J>N+1 Nothing will happen as the largest number is at A[I]

Not part of the proof but to make it clear we get: - for J<x A[J]<A[I] - for J=x A[J]=A[I] - for J<x A[J]>=A[I] and the list is ordered for the first J elements

After j ranges from 1 to i, it will still be the case that the values from 1 to i are sorted. So you can assume that j starts at i without disturbing the induction condition.

The reason this is true is... If A[i] is >= any element A[j] for j < i, then it is clearly true. Otherwise, there is some smallest j in 1 to i-1 inclusive such that A[i] < A[j]. Then A[i] will swap with that A[j], then it will swap again with the next A[j+1] (because the original A[j] was < A[j+1]) by the induction case, then with the next element, ... swapping with every element until j reaches i.

After this is done we have maintained the condition that A[1] .. A[i] are sorted after j ranges from 1 to i.

Clojure code:

    (defn swap [items i j]
      (assoc items
             i (items j)
             j (items i)))
    
    (defn weirdsort [items]
      (let [ct (count items)
            indices (for [i (range ct)
                          j (range ct)]
                      [i j])]
        (reduce (fn [items [i j]]
                  (let [ith (nth items i)
                        jth (nth items j)]
                    (if (< ith jth)
                      (swap items i j)
                      items)))
                items indices))
      )

    my-namespace> (def items (shuffle (range 20)))
    #'my-namespace/items
    my-namespace> items
    [19 0 13 16 14 18 15 7 10 17 9 11 6 1 3 4 12 2 5 8]
    my-namespace> (weirdsort items)
    [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19]

This one is kind of special, though, since it's somehow more offensive to intuition than bubble sort itself.

The issue was the device was so low in memory (2MB of unified NV and flash for code, files and operating memory) that there simply did not exist enough space for a lot of things to be held to be any problem for the 20MHz ARM7 controller as long as you did not do anything stupid. 600kB of it was used by OpenSSL and further 300kB by operating system anyway (I am aware of how funny it sounds when OpenSSL takes twice as much space as OS).

It is not necessarily +10000, it can also be something like x5000.

Because CPUs really, really, really like working short, simple, predictable loops that traverse data in a simple pattern and hate when it is interrupted with something like dereferencing a pointer or looking up a missing page.

So your super complex and super intelligent algorithm might actually be only good on paper but doing more harm to your TLB cache, prefetcher, branch predictor, instruction pipeline, memory density, etc.

So there is this fun question:

"You are generating k random 64 bit integers. Each time you generate the integer, you have to insert it in a sorted collection. You implement two versions of the algorithm, one with a singly-linked list and one with a flat array. In both cases you are not allowed to cheat by using any external storage (indexes, caches, fingers, etc.)

The question: in your estimation, both algorithms being implemented optimally, what magnitude k needs to be for the linked list to start being more efficient than array list."

The fun part of this question is that the answer is: NEVER.

It also explains how to install GNATprove: ``alr with gnatprove``