Insertion Sort using Binary Search

[N.]

Insertion sort is O(N^2), but I figure I can get it in to O(N log2 N)
if the inside loop of the insertion sort is replaced with a binary
search. However, I'm having some implimentation problems...

void insertsort(int a[], int n)
{
int i, j, index;
for (i=0; i < n; i++)
{
index = a;
j=1;
while ((j > 0) && (a[j-1] > index))
{
a[j] = a[j-1];
j = j - 1;
}
a[j] = index;
}
}

The way I figure it, instead of having the inner loop iterate back
through the already sorted array (which takes N-1 in worst-case),
couldn't binary search be used to find the position that the next int
is put in, hence taking the inner loop from some function of N to some
function in log N? Anyone have any details on how to do this?

 

[Alf P. Steinbach]

Insertion sort is O(N^2), but I figure I can get it in to O(N log2 N)
if the inside loop of the insertion sort is replaced with a binary
search.

<ot>
Each insertion is O(n) and you have O(n) insertions, giving O(n^2).

void insertsort(int a[], int n)
{
int i, j, index;
for (i=0; i < n; i++)

First, this loop goes one times too much.

Second, as a matter of good style, use '++i' not 'i++'.

{
index = a;

'index' is a very poor name for a value at a given index.

j=1;
while ((j > 0) && (a[j-1] > index))

What's that "j > 0" doing in there?

Why don't you use a 'for'-loop?

{
a[j] = a[j-1];

Here you copy elements upwards in the array. The first element is
going to get duplicated umpteen times.

j = j - 1;

Here you decrement 'j' which you started off at 1. Why?

}

a[j] = index;
}
}

 

[Andrey Tarasevich]

...
The way I figure it, instead of having the inner loop iterate back
through the already sorted array (which takes N-1 in worst-case),
couldn't binary search be used to find the position that the next int
is put in, hence taking the inner loop from some function of N to some
function in log N? Anyone have any details on how to do this?

It is not really about the search. It is about the insertion that follows.

While using binary search in place of direct iteration will improve the
performance of the implementation, the complexity will still remain at
O(N^2) level since the insertion itself requires O(N) time.

 

[charles8784]

Help

Using binary search on insertion sort. Can anyone please answer the following questions for me?

1 How many key comparisons would be done in the worst case
2 How many times are elements moved in the worst case
3 What is the asymptotic order of the worst case running time
4 can the number of moves be reduced by putting the elements in a linked list instead of an array? Explain