Самый простой (и неожиданный) алгоритм сортировки?

Как сейчас помню, этот алгоритм принес на сдачу одноклассник в 11м классе (93 год), я тогда глядя на него так и не смог осознать, почему он работает, учитель, кажется, тоже был в задумчивости. Где он его взял, не представляю, во всех книгах по программированию, которыми мы обменивались, его не было, интернета тоже не было. Я тогда что-то не спросил, решил что придумал самостоятельно, восхитился (на бумаге выглядит красиво и абсолютно неочевидно). Поэтому как минимум один человек обнаружил его в 1993 году :)

Но сейчас все же думаю что посмотрел где-то или кто-то подсказал

У пузырьковой сортировки меняются местами соседние элементы, а тут два независимых индекса.

О, это очень прикольный алгоритм, и у меня реакция была такой же, когда я первый раз видел статью.
Он, конечно, неэффективный, никто ни спорит
Но прикольным этот алгоритм становится именно тогда, когда пытаешься доказать его корректность.

Смотрите: стандартная сортировка вставками за n^2 устроена так, что каждый раз сравниваются i-й и j-й элементы массива, где i < j. Соответственно после каждого сравнения число инверсий уменьшается.

for i from 0 to n:
  for j from i to n:
    if a[i] > a[j]:
      swap(a[i], a[j])

А в алгоритме из статьи оба цикла от 1 до n, поэтому, иногда (если i > j) алгоритм переставляет элементы, которые уже в правильном порядке. А теперь попробуйте доказать, что после этих операций массив будет отсортирован. Вот и получаем симпатичное упражнение по комбинаторике=)

function sort (arr) {
  for (let i = 1, l = arr.length; i < l; i++) {
    for (let j = 0; j <= (i - 1); j++) {
      if (arr[i] < arr[j]) {
        [arr[i], arr[j]] = [arr[j], arr[i]]
      }
    }
  }
}

Как и пузырёк. За простоту приходится платить.

Upd: я облажался. Всё ещё не стоит статьи, но это не сортировка максимумом.