Comparison sort algorithm

Question

Consider the following algorithm: The given items are inserted one by one into a list by performing comparisons like a binary search for the right position.

Example: Imagine six elements are already sorted in descending order. We now compare the next element to one of the middle elements. Assume it's smaller than #3 (on the left) so we compare it to the middle one of the remaining elements. Assume it's bigger than #5 so we make one last comparison and find it is smaller than #4 so we insert it as the new #5. On the right is another example.

I couldn't find any resources on this, under what name is it known? Thanks in advance.

Answer 1

This is essentially a variant of insertion sort. The general scheme of both algorithms is: mantaian a sorted collection $S$ of elements (initially this collection is empty) and consider one element at a time. When element $x$ is considered, find the position of $x$ in $S$, and add $x$ in that position.

Notice that if you are using an array to back your "list" of elements, then finding the position using binary search rather than linear search is not providing any improvement over the asymptotic computational complexity since inserting an element into $S$ can require $\Omega(|S|)$ time and the overall running time will still be $\Theta(n^2)$.

If you are using an actual list, then you don't have constant-time element access and each binary search still requires roughly $|S|/2 + |S|/4 + |S|/8 = \Theta(|S|)$ operations to locate the elements to compare $x$ with. The running time will still be $\Omega(n^2)$. If you use a doubly-linked list and/or you take some additional care with your implementation, you can match that lower bound with a $O(n^2)$-time algorithm. Otherwise, a naive implementation will require $\Theta(n^2 \log n)$ time.