How to sort an Array Using Insertion Sort DSA

Data Structure / By Rakesh Saini / March 21, 2024

Insertion Sort DSA is a simple sorting algorithm that works in similar way of playing card sorting. This algorithm splits the array into two parts, sorted and unsorted array. Values from unsorted parts are picked and placed into the correct place in sorted array.

Let have try the Algorithm

For example we have an array: [12, 11, 13, 5, 6], consider these elements for all examples.

Explanation:

Iteration 1 (i = 1): Key = 11
- Compare 11 with 12, since 11 < 12, shift 12 to the right.
- Insert 11 at the correct position, which is index 0.
- Array after iteration 1: [11, 12, 13, 5, 6]
Iteration 2 (i = 2): Key = 13
- Compare 13 with 12, no shifting needed.
- Insert 13 at the correct position, which is index 2.
- Array after iteration 2: [11, 12, 13, 5, 6]
Iteration 3 (i = 3): Key = 5
- Compare 5 with 13, 12, and 11. Shift 13, 12, and 11 to the right.
- Insert 5 at the correct position, which is index 0.
- Array after iteration 3: [5, 11, 12, 13, 6]
Iteration 4 (i = 4): Key = 6
- Compare 6 with 13, no shifting needed.
- Insert 6 at the correct position, which is index 4.
- Array after iteration 4: [5, 6, 11, 12, 13]

Insertion Sort Java DSA


public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        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 = j - 1;
            }
            arr[j + 1] = key;
        }
    }
    
    //main function
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        insertionSort(arr);
        System.out.print("Sorted array: ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

//output:
Sorted array: 5 6 11 12 13

JavaScript


function insertionSort(arr) {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    let key = arr[i];
    let j = i - 1;

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

let arr = [12, 11, 13, 5, 6];
insertionSort(arr);
console.log("Sorted array: " + arr);


//output
Sorted array: 5,6,11,12,13

Dart


void insertionSort(List<int> arr) {
    //getting lenght of the array
  int n = arr.length;
  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 = j - 1;
    }
    arr[j + 1] = key;
  }
}

//main fuction
void main() {
  List<int> arr = [12, 11, 13, 5, 6];
  insertionSort(arr);
  print("Sorted array: $arr");
}

//output
Sorted array: [5, 6, 11, 12, 13]