Question

Consider the insertion-sort algorithm: http://ideone.com/XE55P (warning: C code)

in the inner for-loop, which scans through the sorted left part of the array A[0..i-1] using linear search looking for the correct position to insert the current key.

Can we use a binary search there instead?

Answer 1

Yes, you can use binary search.

Answer 2

how will binary search improve the worst-case running time of insertion sort?

Answer 3

will it be \(\large{\Theta}(n\logn)\)

Answer 4

Yes, I think so. I have studied a little of it, but I'm not an expert.

Answer 5

Try the following C++ code.
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int list[] = {7, 6, 5, 4, 3, 2, 1};
int n = 7; //number of list elements
int m;
for (int j = 1; j < n; j++) {
int i = 0;
int left, right, m, s;

//binary search
left = 0;
right = j;
while (left < right) {
m = floor((left + right)/2);
if (list[j] > list[m]) left = m + 1; else right = m;
}
i = left; //i is the index of the new position of list[j]
s = list[j]; //save list[j]

cout << j << " " << i << "\n";

//swap
if (i != j){
cout << "for 0 to " << j - i - 1 << "\n";
for (int k = 0; k <= j - i - 1; k++){
list[j-k] = list[j-k-1];}
list[i] = s;
}
}
//output
for (int pos = 0; pos < n; pos++)
cout << list[pos] << "\t";
system("pause");
return 0;
}

Answer 6

eek! C++! :-D

alright. So I just replace the inner loop with a binary search to locate the correct index for the key, and then swap the key with the element at the right index?

Answer 7

Yes, I think that should be enough. Try it and see if it works.

Answer 8

I'll do it tomorrow... I'm tired of sorting algorithms I spent half a day trying to understand and get merge_sort to work!

Answer 9

OK.