Mi codigo de ordenacion por insercion no funciona bien

[aguml]

Sí, eso ya lo hice y funciona pero la idea era hacerlo de otra forma como sigue. Imagina un arreglo con 1 millón de elementos a insertar en orden, con tu método tienes que leer todo cada vez hasta encontrar su posición y eso cuantos más elementos más tardará.
Mi idea es esta
Si tengo ya los elementos:
1,2,5,6,7,10,15,20
Quiero insertar 9.
La posición inicial será la última con lo que en primer lugar lo comparo con el 20.
Como es menor divido el índice entre 2 para comparar con el del medio que en este caso sería el 6.
Como 9 es mayor que 6 la idea es coger el rango entre la posición actual y la última y comparar con el del centro. En este caso sería con el valor 10 y como 9 es menor coger el rango entre el valor 6 y el 10 y divido entre 2 y esta vez comparará con el 7 y como es mayor cojo el rango de los valores del 7 al 10 y lo divido entre 2 y ya obtendría la posición correcta.
Parece un lio pero pienso que cuando se trabaje con arrais muy grandes puede mejorar los tiempos con respecto a lo que indicas pero no doy con la tecla. He estado dándole muchas vueltas y ahora mismo la tengo así la función que obtiene la posicion pero no funciona a como quiero:

Código PHP:

int buscarPos(int valor, int array[], int size_array) 
{ 
    int pos=size_array,aux_pos; 
    if (size_array > 0){
        do{ 
            aux_pos=pos; 
            if (valor > array[pos-1]){
                if (aux_pos == pos || valor < array[pos]){ 
                    break;
                }else {
                    pos = size_array - (size_array -pos)/2;
                }
            }else if (valor < array [pos-1]){
                size_array = pos;
                pos = size_array / 2;
                if(aux_pos==pos){
                    break;
                }
            }else {
                break;
            }
        }while(aux_pos != pos); 
    }
    return pos; 
}