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

Original Article ↗ Hacker News Discussion ↗

A short 2021 paper analyzes an extremely simple sorting algorithm: two nested loops that compare every pair of elements and swap them when the first is smaller, yet still end up with a correctly sorted array. Commenters dissect why this counterintuitive “swap when less-than” approach actually works, how it relates (and doesn’t relate) to bubble sort, insertion sort, and sorting networks, and why its simplicity makes it both a common beginner’s mistake and an interesting teaching example despite its Θ(n²) inefficiency. Several point out that the work highlights the gap between intuitive code and formal correctness, and illustrates both the value and the limits of non–peer-reviewed venues like arXiv.

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