[C] Insertion-sort velocizzato con ricerca binaria

[vncnz]

Salve! Sono iscritto alla facoltà di informatica (università) e ho questo esercizio da svolgere: "L’insertion Sort non trae vantaggio dal fatto che gli elementi a[0..i-1] sono già ordinati. Utilizzare una ricerca binaria per accelerare la ricerca del punto di inserzione".
Io il programma l'ho creato, funziona, ma è più lento dell'insertion-sort originale. D'altronde l'insertion sort normale cercando il punto di inserzione sposta gli elementi, se io cerco il punto di inserzione con la ricerca binaria devo comunque passare il pezzo di array di cui devo far slittare gli elementi!
Qualcuno potrebbe darmi suggerimenti (il programma completo me lo scrivo io senza problemi) su come fare per migliorarlo?

Il cuore del mio programma è:
int i, j, lower, middle, upper, tmp;
for(i=2; i<fine; i++)
{
lower=0;
tmp=array[i];
upper=i;
do
{
middle=(upper+lower)/2;
if(array[middle]<tmp)
lower=++middle;
else
{
for(j=upper-1; j>=middle ; j--) array[j+1]=array[j];
upper=middle;
}
} while(lower!=upper);
array[middle]=tmp;
}
dove "fine" è la dimensione dell'array da ordinare.