473,372 Members | 1,242 Online

# Insertion Sort using Binary Search

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[i];
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?
Jul 22 '05 #1
2 6751
On 26 Jan 2004 13:09:13 -0800, ba*****@hotmail.com (N.) wrote:
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).
</ot>

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[i];
'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;
}
}

Jul 22 '05 #2
N. wrote:
...
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.

--
Best regards,
Andrey Tarasevich

Jul 22 '05 #3

This thread has been closed and replies have been disabled. Please start a new discussion.