Insertion sort

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 ${displaystyle O(n^{2})}$ operaciones para ordenar una lista de ${displaystyle n}$ elementos.

Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay ${displaystyle k}$ elementos ordenados de menor a mayor, se toma el elemento ${displaystyle 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) o cuando ya no se encuentran elementos (todos los elementos fueron desplazados y este es el más pequeño). En este punto se inserta el elemento ${displaystyle k+1}$ debiendo desplazarse los demás elementos.

En el mejor de los casos, el arreglo está inicialmente en orden, el algoritmo solo hace una pasada entonces la complejidad es ${displaystyle O(n)}$.^[1]​ Y en el peor caso con el arreglo ordenado con el criterio contrario se obtiene una complejidad temporal cuadrática, del orden de ${displaystyle O(n^{2}/2)}$

Martínez Vidal (2006). Introducción al análisis de algoritmos. Consultado el 22 de junio de 2020. 

---