Extraer es constante, no lineal: O(2) = O(1). Pero que sí, que se puede hacer lineal llevando el max y el cuasi_max a la par.

Lo mejor para entender como funciona sería una explicación gráfica. Así que te recomiendo algún pdf o algún vídeo incluso mejor.

Pongo el código para que lo puedas leer mejor:

Ordenación por inserción:

void ord_ins(int v[], int n) {
    int i,j,x;
    for (i=1;i<n;i++) {
        x = v[i];
        j = i-1;
        while ( (j>-1) && (v[j]>x) )
            v[j+1] = v[j--];
        v[j+1] = x;
    }
}

índices del vector: 0..N-1 y ordenación ascendente

Bueno supongamos que tenemos el array { 7, 2, 6, 4, 8, -3 }

1º. Suponemos que el primer elemento está ordenado.

2º. Recorremos el array desde 1 hasta N-1, porque el primer elemento suponemos que está ordenado.

3º. Entonces teniendo en cuenta el for de 1 a N-1, en cada iteración del for escogeremos el elemento . Es decir, en la primera iteración el 2, en la siguiente al 6, en la siguiente al 4... Es decir x =
4º Insertamos ordenadamente x en el subvector generado por los índices 0 e i-1. En este caso insertar x en el subvector { 7 }, porque va desde 0 a i-1, y como i vale 1, pues es el subvector array(0..0). Como 2 es menor que siete, lo insertamos delante.

array { 2, 7, 6, 4, 8, -3 } Hay que mover el 7 a la derecha y el 2 situarlo en la primera posición

5º Volvemos al paso 3 hasta terminar el ciclo for

-> { 2, 7, 6, 4, 8, -3 } seleccionamos el 6 e insertamos en { 2, 7 } => { 2, 6, 7, 4, 8, -3 }

-> { 2, 6, 7, 4, 8, -3 } seleccionamos el 4 e insertamos en { 2, 6, 7 } => { 2, 4, 6, 7, 8, -3 }

-> { 2, 4, 6, 7, 8, -3 } seleccionamos el 8 e insertamos en { 2, 4, 6, 7 } => { 2, 4, 6, 7, 8, -3 } <= El elemento está ya ordenado

-> { 2, 4, 6, 7, 8, -3 } seleccionamos el -3 e insertamos en { 2, 4, 6, 7, 8 } => { -3, 2, 4, 6, 7, 8,} <= Vualá, vector ordenado

Recuerda que para cada inserción tenemos que mover todos los elelementos desde la posición donde vamos a insertar hasta i-1 una posición hacia adelante.

Saludos y espero que lo entiendas.