Assume a list $L$ is to be sorted using the following variation of insertion sort: For $2 \le i \le n$, to insert key $L[i]$ do a binary search on the list $L[1..i-1]$ to find the correct position.

How many key comparisons are done in the worst case?

I think the worst case is when $L$ is sorted in reverse order, which means each index $i$ from $i = 2$ to $n$ would require $2(\lg(i) + 1)$ key comparisons, which is $2[\sum\limits_{i=2}^n lg(i) + (n - 1)]$. I'm pretty sure that is incorrect because I've never seen a summation like that and have no idea how to solve it.

What is the total number of times keys are moved in the worst case?

I think this would be $\lg(i)$ moves on each iteration, or $\sum\limits_{i=2}^n lg(i)$.

Am I on the right track?

  • $\begingroup$ Binary search on lists? How are you going to do that? $\endgroup$ – Raphael Feb 22 '15 at 10:53
  • $\begingroup$ I assumed it was implemented as an array, although my professor didn't feel the need to specify that. The question was asked exactly as given. $\endgroup$ – woodenToaster Feb 22 '15 at 21:36
  • $\begingroup$ Well, technically, analysing key comparisons work the same either way. The algorithm would have worse performance on lists, with all that traversing, but the number of key comparisons would be the same. $\endgroup$ – Raphael Feb 23 '15 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.