Método de ordenación por inserción

El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos.

Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha). En este punto se inserta el elementok+1 debiendo desplazarse los demás elementos.

Ejemplo en c++:

template <class T> void insertionSort(std::vector<T>& v, int fin) {
    int i, j, index;
    for (i=1; i <fin; i++)
 {
        index = v.at(i);
        j = i-1;
        while (j >= 0 && v.at(j)>index) {
            v.at(j+1)=v.at(j);
            j--;
        }
        v.erase(v.begin()+j+1);
        v.insert(v.begin()+j+1,index);
    }
}