Is this the simplest (and most surprising) sorting algorithm ever? (2021)

What the algorithm is doing

• Double loop over all index pairs; if A[i] < A[j] then swap A[i] and A[j].
• Always does exactly n² comparisons, even on already-sorted input.
• Swaps even when elements are already in correct relative order, which feels “wrong” to many readers.
• First outer pass moves the maximum element into position 1; subsequent passes keep reshuffling but still converge to a sorted array.

Relation to known sorting algorithms

• Many commenters initially claim it is “just unoptimized bubble sort,” but others strongly dispute this:
  • Bubble sort only swaps adjacent elements, stops when no swaps occur, and usually uses i < j ranges; this algorithm does none of that.
• Several argue it’s closer to insertion sort:
  • Outer loop gradually grows a sorted prefix.
  • Each new element is effectively “inserted” into the prefix, but via swaps and a reversed comparison.
• Others connect it to “exchange sort” or trivial sorting networks; one mentions the paper itself derives insertion-like and exchange-like variants by tweaking indices.

How/why it works (intuitions and proofs)

• One common invariant: after iteration i of the outer loop, the first i elements are sorted.
• Explanations based on:
  • First pass establishing a sentinel (the global max) at the start.
  • Later passes bubbling/inserting the current A[i] into the correct place within the already-sorted prefix, while the max keeps ending up at the right edge of that prefix.
• Several people only gained intuition after stepping through code or watching visualizations; the behavior is widely described as non-intuitive.

Practicality and use cases

• Time is Θ(n²) in all cases; not stable; bad for external or online sorting; doesn’t exploit partial order.
• Some still use similarly simple double-loop sorts as “quick and dirty” solutions for small n (e.g., coding challenges, toy languages), valuing trivial implementation over performance.
• Others argue more standard simple sorts (insertion, selection, exchange) are equally simple but less confusing.

Novelty, publication, and style

• Several see it as old folklore, not publication-worthy; arXiv’s non–peer-reviewed nature is emphasized.
• Others appreciate a formal correctness proof and the paper’s clear, self-deprecating tone.
• Side discussion on single-author papers using “we” (the “royal we” including reader or community).