0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Since it is a list and not an array, you can not just pick the middle element in $O(1)$ time. $\endgroup$ Sep 23, 2021 at 13:14
  • $\begingroup$ @InuyashaYagami why? $\endgroup$
    – Christian
    Sep 23, 2021 at 15:53
  • $\begingroup$ @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. $\endgroup$
    – Steven
    Sep 24, 2021 at 9:08

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 23, 2021 at 13:54
  • $\begingroup$ Yes :) But if you already have a balanced BST implementation available you might as well push all the input elements in and then read them in sorted order by performing an in-order visit. $\endgroup$
    – Steven
    Sep 23, 2021 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.