Insertion Sort in Java

`Insertion Sort` is the simple algorithm for sorting elements of small datasets. In `Insertion sort` algorithm, the array element is removed and then located at the position it belongs by comparing values. As the complexity of this algorithm is `O(n*2)` where n is the number of elements. You can not use this algorithm for large datasets. In this article, you are going to learn the Insertion sort algorithm program in Java.

Program

```// Program for insertion sort in java

public class InsertionSortInJava {
public static void main(String a[]){
// array to ort
int[] items = {12,1,67,0,-1,-50,90,21};

// printing array before insertion sort
System.out.println("Array before insertion sort");
for(int i:items){
System.out.print(i+" ");
}
System.out.println("\n");

// sorting array by using insertion sort
int n = items.length;
for (int i = 1; i < n; i++) { int key = items[i]; int j = i-1; while ( (j > -1) && ( items[j] > key ) ) {
items[j+1] = items[j];
j--;
}

items[j+1] = key;
}

// printing array after insertion sort
System.out.println("Array after insertion sort");
for(int i:items){
System.out.print(i+" ");
}
}
}
```

The output should be:

Array before insertion sort
12 1 67 0 -1 -50 90 21Array after insertion sort
-50 -1 0 1 12 21 67 90