"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.