3 ms·
Extremely simple sort algorithm with sub-cubic expected running time. [pdf]
- amichail 17y agoAlgorithm: 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.
- jibiki 17y agoYes, they get their bound by counting inversions. This is much better than the method I suggested in the other thread (which, of course, doesn't actually work.)
- swolchok 17y agomy 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.
- codeodor 17y agoI came to say the same. What could be simpler than the O(n^2) algorithms?
- codeodor 17y ago"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.
- amichail 17y agoThat's not the algorithm I'm referring to.