Migliore algoritmo di ordinamento per un array particolare

[pcg4m3s]

Salve,
sapete qual'è il migliore algoritmo di ordinamento nel caso in cui ho un array di N elementi in cui sono sicuro che dall'elemento 1 all'elemento N-1 l'array è già ordinato, l'unico elemento non ordinato è lo 0.

ad esempio se N=8

15 2 3 5 8 10 22 43

come vedete dal numero 2 al numero 43 l'array è già ordinato, l'unico a non esserlo è il 15.

grazie!

[fagix]

Si ok ma che linguaggio di programmazione stai trattando...

[MItaly]

Effettua una ricerca binaria nella parte ordinata dell'array fino ad individuare la posizione dove andrà messo l'elemento non ordinato. A quel punto sposta indietro di una posizione la parte dell'array prima del posto del nuovo elemento e inserisci lì quest'ultimo.