Master Insertion Sort - Adaptive O(n) Algorithm

function insertionSort(arr) {
    /**
     * Insertion Sort - Adaptive O(n²) algorithm
     * Time: O(n²) average/worst, O(n) best (sorted)
     * Space: O(1) - in-place sorting
     * Stable: Yes, Adaptive: Yes, Online: Yes
     */
    const n = arr.length;

    // Start from second element (first is considered sorted)
    for (let i = 1; i < n; i++) {
        let key = arr[i];  // Element to insert
        let j = i - 1;

        // Shift elements of sorted region right
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        // Insert key at correct position
        arr[j + 1] = key;
    }

    return arr;
}

// Usage examples
const arr1 = [12, 11, 13, 5, 6];
console.log(insertionSort(arr1)); // [5, 6, 11, 12, 13]

// Best case - already sorted (O(n))
const arr2 = [1, 2, 3, 4, 5];
console.log(insertionSort(arr2)); // Only n-1 comparisons

// Nearly sorted - adaptive advantage
const arr3 = [1, 2, 4, 3, 5];
console.log(insertionSort(arr3)); // Few shifts needed

package main

import "fmt"

// InsertionSort sorts an array using insertion sort algorithm
// Time: O(n²) average/worst, O(n) best (sorted)
// Space: O(1) - in-place sorting
// Stable: Yes, Adaptive: Yes, Online: Yes
func InsertionSort(arr []int) []int {
    n := len(arr)

    // Start from second element (first is considered sorted)
    for i := 1; i < n; i++ {
        key := arr[i]  // Element to insert
        j := i - 1

        // Shift elements of sorted region right
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j--
        }

        // Insert key at correct position
        arr[j+1] = key
    }

    return arr
}

func main() {
    // Usage examples
    arr1 := []int{12, 11, 13, 5, 6}
    fmt.Println(InsertionSort(arr1))
    // Output: [5 6 11 12 13]

    // Best case - already sorted (O(n))
    arr2 := []int{1, 2, 3, 4, 5}
    fmt.Println(InsertionSort(arr2))
    // Only n-1 comparisons

    // Nearly sorted - adaptive advantage
    arr3 := []int{1, 2, 4, 3, 5}
    fmt.Println(InsertionSort(arr3))
    // Few shifts needed
}

public class InsertionSort {
    /**
     * Insertion Sort - Adaptive O(n²) algorithm
     * Time: O(n²) average/worst, O(n) best (sorted)
     * Space: O(1) - in-place sorting
     * Stable: Yes, Adaptive: Yes, Online: Yes
     */
    public static void insertionSort(int[] arr) {
        int n = arr.length;

        // Start from second element (first is considered sorted)
        for (int i = 1; i < n; i++) {
            int key = arr[i];  // Element to insert
            int j = i - 1;

            // Shift elements of sorted region right
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }

            // Insert key at correct position
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        // Usage examples
        int[] arr1 = {12, 11, 13, 5, 6};
        insertionSort(arr1);
        System.out.println(Arrays.toString(arr1));
        // Output: [5, 6, 11, 12, 13]

        // Best case - already sorted (O(n))
        int[] arr2 = {1, 2, 3, 4, 5};
        insertionSort(arr2);
        // Only n-1 comparisons

        // Nearly sorted - adaptive advantage
        int[] arr3 = {1, 2, 4, 3, 5};
        insertionSort(arr3);
        // Few shifts needed
    }
}

#include <iostream>
#include <vector>
using namespace std;

/**
 * Insertion Sort - Adaptive O(n²) algorithm
 * Time: O(n²) average/worst, O(n) best (sorted)
 * Space: O(1) - in-place sorting
 * Stable: Yes, Adaptive: Yes, Online: Yes
 */
void insertionSort(vector<int>& arr) {
    int n = arr.size();

    // Start from second element (first is considered sorted)
    for (int i = 1; i < n; i++) {
        int key = arr[i];  // Element to insert
        int j = i - 1;

        // Shift elements of sorted region right
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        // Insert key at correct position
        arr[j + 1] = key;
    }
}

int main() {
    // Usage examples
    vector<int> arr1 = {12, 11, 13, 5, 6};
    insertionSort(arr1);

    for (int num : arr1) {
        cout << num << " ";
    }
    // Output: 5 6 11 12 13

    cout << endl;

    // Best case - already sorted (O(n))
    vector<int> arr2 = {1, 2, 3, 4, 5};
    insertionSort(arr2);
    // Only n-1 comparisons

    return 0;
}