ICan’tBelieveItCanSort!

I recently learned a new sorting algorithm called the ICan’tBelieveItCanSort algorithm:

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        if (A[i] < A[j])
            swap(A[i], A[j]);

Wait what? The more I think about this, the more I think it shouldn’t work. This sorts in increasing order?

But it does actually work, and I think watching a visualization is the best way to convince yourself.

I still can’t believe it can sort! But this algorithm does have a certain aesthetic elegance so I definitely encourage you to use it in all your programs to troll the next person who reads your code!

You can read more about this algorithm and a formal proof of it in this arXiv paper.