Extremely simple sort algorithm with sub-cubic expected running time. [pdf]

Algorithm: Pick two elements at random. If they are out of order, swap them. Could check every n-1 steps to see whether array is sorted.

Expected running time is O(n^2 log(n)).

See Section 3.

"Usually, binary search only makes sense in sorted arrays. We show that insertion sort based on repeated “binary searches” in an initially unsorted array also sorts n elements in time Theta(n^2 log n)."

At first I thought this is unsurprising - an insertion sort being n^2 and a search being log n, of course that's the running time.

But it's not the running time that is worth of mention here - it's the fact that they are doing insertion sort while "binary searching" an unsorted array, and still coming up with the correct answer, and a sorted array.

The time complexity is incidental to the interest of the paper. In that view, the paper's title is much better than the title here on HN.

my gut says this is ridiculous given that it's asymptotically slower than insertion sort, selection sort, and bubble sort and doesn't take advantage of cache (through sequential access) the way those algorithms do.