Insertion Sort

Easy

Python

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

Java

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

Key Insight

Most similar sorting. j-=1 vs j--.

Python → Java Differences

j-=1 vs j--
range(1,len) vs i<len
Logic nearly identical

Python

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

Java

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

Algorithm Steps

1. For each element
2. Shift larger right
3. Insert at correct position

← Previous All Sorting Next →