Insertion Sort Program with Explanation and Code

2025-11-04 insertion sort sorting algorithm python c c# js php

Learn how the Insertion Sort algorithm works with a simple explanation, step-by-step logic, and code examples in Python, C, JavaScript, PHP, and C#. Perfect for students and interview preparation.

Program Explanation

What is Insertion Sort?

Insertion Sort is a simple and efficient comparison-based sorting algorithm. It builds the final sorted array one element at a time, similar to how playing cards are sorted in a hand.

Steps to Solve

  1. Start from the second element of the array (index 1).
  2. Store the current element in a temporary variable (key).
  3. Compare the key with elements to its left.
  4. Shift all elements that are greater than the key to one position ahead.
  5. Insert the key in its correct sorted position.
  6. Repeat this process for all array elements.
  7. Finally, the array becomes fully sorted.

Explain The Program Line By Line (Algorithm)

  1. Read the number of elements and the array from the user.
  2. Loop from index 1 to the end of the array.
  3. Store the current element as key.
  4. Compare the key with elements before it.
  5. Shift elements greater than key to the right.
  6. Place key in its correct position.
  7. Continue this until the entire array is sorted.

Key Points

  • Best for small datasets.
  • Efficient for nearly sorted arrays.
  • Worst-case time complexity: O(n²).
  • Best-case time complexity: O(n).
  • Stable and in-place sorting algorithm.

Program Code


arr = list(map(int, input("Enter numbers: ").split()))

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

print("Sorted array:", arr)
      

#include <stdio.h>

int main() {
    int n, i, j, key;

    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter elements: ");
    for(i = 0; i < n; i++) scanf("%d", &arr[i]);

    for(i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        while(j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }

    printf("Sorted array: ");
    for(i = 0; i < n; i++) printf("%d ", arr[i]);

    return 0;
}
      

let arr = prompt("Enter numbers:").split(" ").map(Number);

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;
}

console.log("Sorted array:", arr);
      

using System;

class Program {
    static void Main() {
        Console.Write("Enter numbers: ");
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        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;
        }

        Console.Write("Sorted array: ");
        foreach (int num in arr)
            Console.Write(num + " ");
    }
}
      

<?php
$arr = explode(" ", readline("Enter numbers: "));

for ($i = 1; $i < count($arr); $i++) {
    $key = $arr[$i];
    $j = $i - 1;

    while ($j >= 0 && $arr[$j] > $key) {
        $arr[$j + 1] = $arr[$j];
        $j--;
    }

    $arr[$j + 1] = $key;
}

echo "Sorted array: " . implode(" ", $arr);
?>
1