Skip to content(if available)orjump to list(if available)

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

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

15 comments

·February 24, 2025
Visit

javierlc

This is well known (google trivial sorting network!), and it would never be published anywhere peer-reviewed.

Good reminder that Arxiv is not peer-reviewed :/

ColinWright

Formatted:

For easier exposition in the proof later on, the array is 1-based, so the elements are A[1]...A[n].

    Algorithm 1

    ICan’tBelieveItCanSort(A[1..n])
      for i = 1 to n do
        for j = 1 to n do
          if A[i] < A[j] then
            swap A[i] and A[j]

AnimalMuppet

Isn't that just BubbleSort?

And, if so: they're writing Arxiv papers on BubbleSort now?

kccqzy

Bubble sort only swaps adjacent elements—that's why it's called bubble. This doesn't.

GuB-42

It is not, it is actually closer to a selection sort.

The interesting part is that it often comes up when the one writing the algorithm doesn't know what he is doing, and yet, it works. It may look like a BubbleSort because it is a common wrong implementation of BubbleSort.

codr7

BubbleSort keeps going until no more swaps happen, this algorithm specifies up front which items to compare.

I actually think it's pretty cool, it happens occasionally that I just need a quick and dirty sort and this is easier to get right.

sorokod

Note the:

    A[i] < A[j]

deepspace

You did not bother to read the article, did you?

skeaker

No.

tromp

Previous discussion: https://news.ycombinator.com/item?id=28758106

dang

Thanks! Macroexpanded:

Is this the simplest (and most surprising) sorting algorithm? - https://news.ycombinator.com/item?id=28758106 - Oct 2021 (318 comments)

phkahler

Question on paper writing... There is only one author listed, but the wording keeps using "we" as in "we show that..." Is it considered poor practice to use "I" in a one-person paper? Or is "we" including the reader in the exposition?

berbec

Algorithm 1 ICan’tBelieveItCanSort(A[1..n]) for i = 1 to n do for j = 1 to n do if A[i] < A[j] then swap A[i] and A[j]

dang

For code formatting, you can prepend two spaces to a line (this is in https://news.ycombinator.com/formatdoc).

(That's what ColinWright did at https://news.ycombinator.com/item?id=43162234 for example.)

y-curious

Feels oddly familiar; I'm pretty sure this was the optimal solution to a leetcode problem (with specific constraints) that I saw during interview practice. Coming up with this on the fly during an interview would have been extra impressive.