Let’s learn insertion sort java with an example.

## Insertion sort in java

Insertion sort sorts elements the way in which we sort (playing) cards. It is useful when number of elements is small. Given an array of elements, let’s sort them in increasing order.

Also read – merge sort in java

So let’s look at sample list of integer elements. We have a list of six elements that we want to sort and we will number them from 0 to 5.

**Insertion sort algorithm:**

First element 50 is already sorted because insertion sort sorts from the left. So the definition of sorted means that all elements to the left of an element are smaller than that element.

So you can see element 50 at index 0 has no element to the left of it that is larger than 50. Therefore 50 is already sorted.

We will start our insertion sort at index 1 which is 80. So we will set our key value x = 80. Now our first comparison is to the element which is to the left of key value, that is, 50.

And the comparison is x < 50? In other words, is 80 < 50? No it’s not. So, 80 is going to stay where it is. 80 is now considered sorted.

Then we will look at index 2 in our list which is 10. We will assign x = 10, our first comparison, is x < 80? Yes it is, 10 < 80. So swap 80 and 10.

Key does not change though. “x” value is still 10. So our next comparison, is 10 < 50? Yes it is, so swap 50 and 10.

Now we can see that we started at index 2 and index 2 is now sorted. So we are going to jump our pointer to index 3 which is 30.

So, we set our key value x = 30. Our first comparison, is x < 80? Yes it is, so it’s going to swap 30 and 80. Next comparison, is 30 < 50? Yes, it’s going to swap those two.

Next comparison, is 30 < 10? No it’s not, so we are done sorting upto index 3. As you can see at this point we have sorted four elements from index 0 through 3 and you can that see each one of values to its left are all smaller.

Also read – selection sort program in java

So the values to the left of 80 are all smaller. Our next element in the list is 90, we set x = 90. Our first comparison, is x < 80? Well no it’s not and since we already know that all the elements to the left of 80 are smaller than 80 since the list is sorted.

Then they are also less than 90. So we know that 90 is already done. So we are going to move on to index 5 which is 60.

We set x = 60. Our first comparison, is 60 < 90? Yes it is, swap them. Next comparison, is 60 < 80? Yes it is, swap 60 and 80.

Next comparison, is 60 < 50? No, it is not. So sorting is now finished. We have our sorted array (as shown in above figure). Here’s the java program

### Insertion program

/* * java program to sort an array using insertion sort algorithm */ public class InsertionSort { public void sort(int arrNum[]) { int number = arrNum.length; for(int a = 1; a < number; ++a) { int keyValue = arrNum[a]; int b = a - 1; while(b >= 0 && arrNum[b] > keyValue) { arrNum[b + 1] = arrNum[b]; b = b - 1; } arrNum[b + 1] = keyValue; } } static void displayArray(int arr[]) { int num = arr.length; for(int a = 0; a < num; ++a) { System.out.print(arr[a] + " "); } System.out.println(); } public static void main(String[] args) { int[] arrInput = { 50, 80, 10, 30, 90, 60 }; InsertionSort obj = new InsertionSort(); obj.sort(arrInput);displayArray(arrInput); } }

**Output:**

10 30 50 60 80 90

**Time complexity**

It’s O(n*2). This sorting algorithm takes more time if elements in the array is in reverse order.

**Auxiliary space:** O(1)

**Best performance:** O(n) comparison and O(1) swap.

**Worst performance:** O(n²) comparison and swap.

**Average performance:** O(n²) comparison and swap.

**Insertion sort java descending order**

Now let’s learn to sort in reverse order. That is, insertion sort in java descending order.

/* * java program to sort descending order using insertion sort algorithm */ import java.util.Arrays; public class InsertionSortDemo { public static void main(String[] args) { int[] arrInput = { 50, 80, 10, 30, 90, 60 }; System.out.println("Before Sorting: ");displayArray(arrInput);insertionSort(arrInput); System.out.println("\nAfter Sorting: ");displayArray(arrInput); } private static void insertionSort(int[] arrNumber) { for(int a = 1; a < arrNumber.length; a++) { int toSort = arrNumber[a]; int b = a; while(b > 0 && arrNumber[b - 1] < toSort) { arrNumber[b] = arrNumber[b - 1]; b--; } arrNumber[b] = toSort; } } public static void displayArray(int[] arrPrint) { System.out.println(Arrays.toString(arrPrint)); } }

**Output:**

Before Sorting:

[50, 80, 10, 30, 90, 60]

After Sorting:

[90, 80, 60, 50, 30, 10]

**Insertion sort string java**

Here we are going to learn java insertion sort with string array. Here we are going to create method to sort string array using insertion sort.

In sorting string array using insertion sort we are using Comparable interface. Let’s see java program,

import java.util.Arrays; public class InsertionSortString { public static void main(String[] args) { String[] fruits = {"Lemon", "Pineapple", "Tangerine", "NanceFruit", "Cherry"}; System.out.println("String array before sorting : " + Arrays.toString(fruits));insertionSort(fruits); System.out.println("String array after sorting : " + Arrays.toString(fruits)); } public static void insertionSort(Comparable[] objArray) { // insertion sort starts from second element for(int a = 1; a < objArray.length; a++) { Comparable toSort = objArray[a]; int b = a; while(b > 0 && objArray[b - 1].compareTo(toSort) > 1) { objArray[b] = objArray[b - 1]; b--; } objArray[b] = toSort; } } }

**Output:**

String array before sorting : [Lemon, Pineapple, Tangerine, NanceFruit, Cherry]

String array after sorting : [Cherry, Lemon, NanceFruit, Pineapple, Tangerine]