Insertion Sort
- Insertion Sort is a simple and intuitive sorting algorithm that builds the final
sorted array one elementat a time. - It works by taking each element from the input and inserting it into its correct position in the
already sorted part of the array. Starting from the second element, it compares the current element with the previous ones,shifting larger elementsone position ahead to make space for the current element.- This
process continuesuntil all elements are sorted. -
Insertion Sortis efficient forsmallor nearlysorrteddatasets and operates in-place without requiring extra memory.
Approach:
Start from the second element(index 1) since the first element is trivially“sorted”.- Store the current element (curr) and compare it with all
previous elements. Shiftthe previous elements one position forward if they are greater than the current element.Insertthe current element (curr) at its correct sorted position.Repeatuntil the wholearray is sorted.
Time & Space Complexity:
Time Complexity: O(n) Best Case Already Sorted.
Average Case: O(n2)
Worst Case: O(n2)Every element has to be compared and shifted back to the start.
Space Complexity: O(1) No extra array is used; sorting is done in-place.
Dry Run
Input: arr = [4, 5, 1, 3, 9]
i = 1 → curr = 5, prev = 0 arr[0] = 4 ≤ 5 → no shifting Insert curr → [4, 5, 1, 3, 9] i = 2 → curr = 1, prev = 1 arr[1] = 5 > 1 → shift → [4, 5, 5, 3, 9] arr[0] = 4 > 1 → shift → [4, 4, 5, 3, 9] prev = -1 → stop Insert curr → [1, 4, 5, 3, 9] i = 3 → curr = 3, prev = 2 arr[2] = 5 > 3 → shift → [1, 4, 5, 5, 9] arr[1] = 4 > 3 → shift → [1, 4, 4, 5, 9] arr[0] = 1 ≤ 3 → stop Insert curr → [1, 3, 4, 5, 9] i = 4 → curr = 9, prev = 3 arr[3] = 5 ≤ 9 → no shifting Insert curr → [1, 3, 4, 5, 9] Final Sorted Array: [1, 3, 4, 5, 9]
Output: [1, 3, 4, 5, 9]
let arr = [4,5,1,3,9]
function insertionSort(arr){
let n = arr.length;
for(let i=1; i < n; i++) {
let curr = arr[i];
let prev = i - 1;
while(arr[prev] > curr && prev >= 0) {
arr[prev + 1] = arr[prev];
prev--;
}
arr[prev + 1] = curr;
}
return arr;
}
let result = insertionSort(arr);
console.log("Sorted array", result);
def insertionSort(arr):
n = len(arr)
for i in range(1, n):
curr = arr[i]
prev = i - 1
while prev >= 0 and arr[prev] > curr:
arr[prev + 1] = arr[prev]
prev -= 1
arr[prev + 1] = curr
return arr
arr = [4, 5, 1, 3, 9]
print("Sorted array:", insertionSort(arr))
public class Main {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int curr = arr[i];
int prev = i - 1;
while (prev >= 0 && arr[prev] > curr) {
arr[prev + 1] = arr[prev];
prev--;
}
arr[prev + 1] = curr;
}
}
public static void main(String[] args) {
int[] arr = {4, 5, 1, 3, 9};
insertionSort(arr);
System.out.println("Sorted array: " + java.util.Arrays.toString(arr));
}
}
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
for(int i = 1; i < n; i++) {
int curr = arr[i];
int prev = i - 1;
while(prev >= 0 && arr[prev] > curr) {
arr[prev + 1] = arr[prev];
prev--;
}
arr[prev + 1] = curr;
}
}
int main() {
int arr[] = {4, 5, 1, 3, 9};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
cout << "Sorted array: ";
for(int i = 0; i < n; i++) cout << arr[i] << " ";
return 0;
}
#include <stdio.h>
void insertionSort(int arr[], int n) {
for(int i = 1; i < n; i++) {
int curr = arr[i];
int prev = i - 1;
while(prev >= 0 && arr[prev] > curr) {
arr[prev + 1] = arr[prev];
prev--;
}
arr[prev + 1] = curr;
}
}
int main() {
int arr[] = {4, 5, 1, 3, 9};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printf("Sorted array: ");
for(int i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}
using System;
class Program
{
static int[] InsertionSort(int[] arr)
{
int n = arr.Length;
for (int i = 1; i < n; i++)
{
int curr = arr[i];
int prev = i - 1;
// Shift elements greater than curr to one position ahead
while (prev >= 0 && arr[prev] > curr)
{
arr[prev + 1] = arr[prev];
prev--;
}
arr[prev + 1] = curr;
}
return arr;
}
static void Main(string[] args)
{
int[] arr = { 4, 5, 1, 3, 9 };
int[] result = InsertionSort(arr);
Console.WriteLine("Sorted array: " + string.Join(", ", result));
}
}
