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?