# Comparison sort algorithm

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.

• Since it is a list and not an array, you can not just pick the middle element in $O(1)$ time. Sep 23, 2021 at 13:14
• @InuyashaYagami why? Sep 23, 2021 at 15:53
• @Christian. Lists don't support random element indexing in constant time. You have to locate the element you are looking for by traversing the list from an endpoint or some other already known element. Sep 24, 2021 at 9:08

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.
• Right! Adding to your answer: If the list is maintained as balanced BST then such type of insertion gives $\Theta(n \log n)$ time complexity. Sep 23, 2021 at 13:54