Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

Create a Java program to perform an insertion sort and further analyze its efficiency.

1. We will store the random set of numbers in an array.

2. We will traverse this array and insert each element of this array, to its correct position where it should actually be, by shifting the other elements on the left if required.

3. The first element in the array is considered as sorted, even if it is an unsorted array. The array is sub-divided into two parts, the first part holds the first element of the array which is considered to be sorted and second part contains all the remaining elements of array.

4. With each iteration one element from the second part is picked and inserted into the first part of array at its correct position by shifting the existing elements if required.

5. This goes until the last element in second part of array is placed in correct position in the output array.

6. Now, we have the array in sorted order.

**Insertion Sort Example:**

If we have the array as {50,20,60,90,40} and we apply insertion sort to sort the array, then the resultant array after each iteration will be as follows:Original array: {50, 20, 60, 90, 40}Array afterfirstiteration is 20 -> 50 -> 60 -> 90 -> 40 Array afterseconditeration is 20 -> 50 -> 60 -> 90 -> 40 Array afterthirditeration is 20 -> 50 -> 60 -> 90 -> 40 Array afterfourthiteration is 20 -> 40 -> 50 -> 60 -> 90Sorted array is 20 40 50 60 90

Here is the source code of the Java Program to implement Insertion Sort. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

`/*`

`* Java Program to Implement Insertion Sort`

`*/`

import java.util.Scanner;

`/* Class InsertionSort */`

public class InsertionSort

`{`

`/* Insertion Sort function */`

public static void sort( int arr[] )

`{`

int N = arr.length;

int i, j, temp;

for (i = 1; i< N; i++)

`{`

j = i;

temp = arr[i];

while (j > 0 && temp < arr[j-1])

`{`

arr[j] = arr[j-1];

j = j-1;

`}`

arr[j] = temp;

`}`

`}`

`/* Main method */`

public static void main(String[] args)

`{`

Scanner scan = new Scanner( System.in );

System.out.println("Insertion Sort Test\n");

int n, i;

`/* Accept number of elements */`

System.out.println("Enter number of integer elements");

n = scan.nextInt();

`/* Create integer array on n elements */`

int arr[] = new int[ n ];

`/* Accept elements */`

System.out.println("\nEnter "+ n +" integer elements");

for (i = 0; i < n; i++)

arr[i] = scan.nextInt();

`/* Call method sort */`

sort(arr);

`/* Print sorted Array */`

System.out.println("\nElements after sorting ");

for (i = 0; i < n; i++)

System.out.print(arr[i]+" ");

System.out.println();

`}`

`}`

1. Using a for loop, we are reading n elements from standard input into an array named arr.

2. Next, we are comparing elements of the array so that we can insert them in the proper position using the insertion sort method.

3. At the end, we are printing/displaying the sorted array.

**Time Complexity: O(N)**

The worst and average case time complexity of insertion sort algorithm is O(N^{2}) while the best case time complexity of insertion sort is O(N).

**Space Complexity: O(1)**

The space complexity for insertion sort is O(1) if we only consider the order of space used excluding the array.

**Testcase 1:**

Insertion Sort Test Enter number of integer elements 20 Enter 20 integer elements 999 921 823 816 767 712 698 657 532 412 391 323 287 256 225 162 123 64 24 6 Elements after sorting 6 24 64 123 162 225 256 287 323 391 412 532 657 698 712 767 816 823 921 999

**Testcase 2:**

Insertion Sort Test Enter number of integer elements 20 Enter 20 integer elements 12 34 68 79 123 145 178 213 253 276 298 301 498 512 633 792 888 912 950 991 Elements after sorting 12 34 68 79 123 145 178 213 253 276 298 301 498 512 633 792 888 912 950 991

**Testcase 3:**

Insertion Sort Test Enter number of integer elements 20 Enter 20 integer elements 54 135 23 75 1 576 234 928 13 84 631 1283 748 124 54 6 24 485 1024 0 Elements after sorting 0 1 6 13 23 24 54 54 75 84 124 135 234 485 576 631 748 928 1024 1283

To practice programs on every topic in Java, please visit “Programming Examples in Java”, “Data Structures in Java” and “Algorithms in Java”.

**Next Steps:**

- Get Free Certificate of Merit in Java Programming
- Participate in Java Programming Certification Contest
- Become a Top Ranker in Java Programming
- Take Java Programming Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

**Related Posts:**

- Buy Programming Books
- Buy Java Books
- Practice BCA MCQs
- Practice Information Technology MCQs
- Practice Programming MCQs