This Absurdly Simple Sorting Algorithm Shouldn't Work—But It Does

I Can't Believe It Can Sort

A deceptively simple sorting algorithm, named "I Can't Believe It Can Sort," uses just two nested loops and a swap condition to sort an array. Despite its O(n²) time complexity and apparent naivety, it correctly sorts any input. The pseudocode, taken from Stanley P. Y. Fung's paper, challenges intuition and has sparked discussion for its surprising effectiveness.

The reason that it is named so is because if you were to look at the pseudocode, you won't think that it can actually sort but it does.
  1. Someone

    Paper about this with proof of how/why it works: https://arxiv.org/pdf/2110.01111, which says:

    “There is nothing good about this algorithm. It is slow – the algorithm obviously runs in Θ(n2) time, whether worst-case, average-case or best-case. It unnecessarily compares all pairs of positions, twice (but see Section 3). There seems to be no intuition behind it, and its correctness is not entirely obvious. You certainly do not want to use it as a first example to introduce students to sorting algorithms. It is not stable, does not work well for external sorting, cannot sort inputs arriving online, and does not benefit from partially sorted inputs. Its only appeal may be its simplicity, in terms of lines of code and the “symmetry” of the two loops.”

  2. petercooper

    On the topic of fun small sorting algorithms, I was always tickled by "sleep sort":

    a=[5,3,1,4,2];b=[];a.map(n=>setTimeout(()=>b.push(n),n))

    Obviously never use this for real, but I found it fun to think about the behavior and pitfalls of this algorithm in different languages.

  3. senfiaj

    Looks like suboptimal insertion sort.

    After the first nested loop run A[1] will have the largest value.

    After the second nested loop run A[1] will always be swapped with A[2] (unless they are equal, logically doesn't change anything). A[2] now contains the largest value.

    After the k-th (k >= 2) nested loop run, if you pay attention, the k-th element will be inserted into the first k-1 sorted elements. When j >= i, it can no longer do anything, since A[k] will contain the largest value.

    After the k-th (k >= 2) nested loop run the first k elements will be sorted relative to each other. The first nested loop is special by bringing the largest element to A[1], the consecutive ones are just inserting A[k] into the sorted first k - 1 elements from the beginning of the array.

  4. fwlr

    There are two reasons it (intuitively) should not work: one is that the inner for loop also starts from the beginning, without checking where the outer for loop is at, meaning you’ll get `compare(a[0], a[2]) == true` but you’ll also get `compare(a[2], a[0]) == false`, so it would appear you can’t get any useful meaning out of the result of `compare`. The other is that the comparison sign is the wrong way around.

    Somehow, though, these two reasons it shouldn’t work manage to interact in a way that precisely counteract each other, producing a working sort!

  5. smusamashah

    It behaves somewhat like insertion sort https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZ...

    Tick insertion sort on right panel and tap start.

More from this day

2026-11-16