Sorting Algorithms

Insertion Sort Step by Step

Adaptive insertion, semi-sorted lists, and O(N) best case in C, Java, JS, and Python.

1. Adaptive Insertion Mechanics

Insertion Sort builds the final sorted array one item at a time, sliding elements leftward like sorting playing cards.

ALGORITHMIC ANALYSIS

Mejor Caso (Array Casi Ordenado)O(N) lineal

Peor Caso (Invertido)O(N²)

EstabilidadEstable (preserva orden)

2. C: Insertion Sort

Ideal para conjuntos pequeños de datos o vectores casi ordenados.

insertion.c

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

3. Java: Insertion Sort

Utilizado internamente como subrutina en algoritmos híbridos de ordenamiento (Timsort / Dual-Pivot Quicksort) para particiones pequeñas.

InsertionSort.java

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]; j--;
        }
        arr[j + 1] = key;
    }
}

4. JavaScript: Insertion Sort

Procesamiento eficiente de desplazamiento de claves mediante bucle `while`.

insertion.js

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

5. Python: Insertion Sort

Sintaxis directa con bucle `while` decrementando el índice `j`.

insertion.py

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

6. Key Insertion Inspector

Array: [12, 11, 13]

Clave key=11 ➔ Desplaza 12 a pos 1 ➔ Inserta 11 en pos 0 ➔ [11, 12, 13]