**This Tutorial Explains Insertion Sort in Java Including its Algorithm, Pseudo-code, and Examples of Sorting Arrays, Singly Linked and Doubly Linked List:**

The Insertion Sort Algorithm technique is similar to Bubble sort but, is slightly more efficient. Insertion sort is more feasible and effective when a small number of elements is involved. When the data set is larger, it will take more time to sort the data.

**=> Take A Look At The Java Beginners Guide Here.**

What You Will Learn:

## Introduction To Insertion Sort In Java

In the Insertion sort technique, we assume that the first element in the list is already sorted and we begin with the second element. The second element is compared with the first and swapped if not in order. This process is repeated for all the subsequent elements.

In general, the Insertion sort technique compares each element with all of its previous elements and sorts the element to place it in its proper position.

As already mentioned, the Insertion sort technique is more feasible for a smaller set of data, and thus arrays with a small number of elements can be sorted using efficiently Insertion sort.

Insertion sort is especially useful in sorting linked list data structures. As you know, Linked lists have pointers pointing to its next element (singly linked list) and previous element (double linked list). This makes it easier to keep track of the previous and next elements.

Thus it is easier to use Insertion sort for sorting linked lists. However, sorting will take a lot of time if the data items are more.

**In this tutorial, we will discuss the Insertion sort technique including its algorithm, pseudo-code, and examples. We will also implement Java programs to Sort an array, Singly linked list, and Doubly linked list using Insertion sort.**

### Insertion Sort Algorithm

**The insertion sort algorithm is as follows.**

**Step 1**: Repeat Steps 2 to 5 for K = 1 to N-1

** Step 2**: set temp = A[K]

** Step 3**: set J = K – 1

** Step 4**:

Repeat while temp <=A[J]

set A[J + 1] = A[J]

set J = J – 1

[end of inner loop]

**Step 5**:

set A[J + 1] = temp

[end of loop]

**Step 6**: exit

As you know, insertion sort starts from the second element assuming that the first element is already sorted. The above steps are repeated for all the elements in the list from the second element onwards and put in their desired positions.

### Pseudocode For Insertion Sort

**The pseudo-code for the insertion sort technique is given below.**

procedure insertionSort(array,N ) array – array to be sorted N- number of elements begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array[i] freePosition = i //locate free position to insert the element while freePosition > 0 and array[freePosition -1] > insert_val do: array [freePosition] = array [freePosition -1] freePosition = freePosition -1 end while //insert the number at free position array [freePosition] = insert_val end for end procedure

Next, let us see an illustration that demonstrates sorting an array using Insertion sort.

### Sorting An Array Using Insertion Sort

**Let us take an example of Insertion sort using an array.**

The array to be sorted is as follows:

Now for each pass, we compare the current element to all its previous elements. So in the first pass, we start with the second element.

Thus, we require N number of passes to completely sort an array containing N number of elements.

**The above illustration can be summarized in tabular form as shown below:**

Pass | Unsorted list | comparison | Sorted list |
---|---|---|---|

1 | {10,2,6,15,4,1} | {10,2} | {2,10, 6,15,4,1} |

2 | {2,10, 6,15,4,1} | {2,10, 6} | {2,6, 10,15,4,1} |

3 | {2,6, 10,15,4,1} | {2,6, 10,15} | {2,6, 10,15,4,1} |

4 | {2,6, 10,15,4,1} | {2,6, 10,15,4} | {2,4,6, 10,15,1} |

5 | {2,4,6, 10,15,1} | {2,4,6, 10,15,1} | {1,2,4,6, 10,15} |

6 | {} | {} | {1,2,4,6, 10,15} |

As shown in the illustration above, at the end of each pass, one element goes in its proper place. Hence in general, to place N elements in their proper place, we need N-1 passes.

### Insertion Sort Implementation In Java

**The following program shows the implementation of the Insertion sort in Java. Here, we have an array to be sorted using the Insertion sort.**

import java.util.*; public class Main { public static void main(String[] args) { //declare an array and print the original contents int[] numArray = {10,6,15,4,1,45}; System.out.println("Original Array:" + Arrays.toString(numArray)); //apply insertion sort algorithm on the array for(int k=1; k<numArray.length-1; k++) { int temp = numArray[k]; int j= k-1; while(j>=0 && temp <= numArray[j]) { numArray[j+1] = numArray[j]; j = j-1; } numArray[j+1] = temp; } //print the sorted array System.out.println("Sorted Array:" + Arrays.toString(numArray)); } }

**Output:**

Original Array:[10, 6, 15, 4, 1, 45]

Sorted Array:[1, 4, 6, 10, 15, 45]

In the above implementation, it is seen that sorting begins from the 2^{nd} element of the array (loop variable j = 1) and then the current element is compared to all its previous elements. The element is then placed in its correct position.

Insertion sort works effectively for smaller arrays and for arrays that are partially sorted where the sorting is completed in fewer passes.

Insertion sort is a stable sort i.e. it maintains the order of equal elements in the list.

### Sorting A Linked List Using Insertion Sort

**The following Java program shows the sorting of a singly linked list using the Insertion sort.**

import java.util.*; class Linkedlist_sort { node head; node sorted; //define node of a linked list class node { int val; node next; public node(int val) { this.val = val; } } //add a node to the linked list void add(int val) { //allocate a new node node newNode = new node(val); //link new node to list newNode.next = head; //head points to new node head = newNode; } // sort a singly linked list using insertion sort void insertion_Sort(node headref) { // initially, no nodes in sorted list so its set to null sorted = null; node current = headref; // traverse the linked list and add sorted node to sorted list while (current != null) { // Store current.next in next node next = current.next; // current node goes in sorted list Insert_sorted(current); // now next becomes current current = next; } // update head to point to linked list head = sorted; } //insert a new node in sorted list void Insert_sorted(node newNode) { //for head node if (sorted == null || sorted.val >= newNode.val) { newNode.next = sorted; sorted = newNode; } else { node current = sorted; //find the node and then insert while (current.next != null && current.next.val < newNode.val) { current = current.next; } newNode.next = current.next; current.next = newNode; } } //display nodes of the linked list void print_Llist(node head) { while (head != null) { System.out.print(head.val + " "); head = head.next; } } } class Main{ public static void main(String[] args) { //define linked list object Linkedlist_sort list = new Linkedlist_sort(); //add nodes to the list list.add(10); list.add(2); list.add(32); list.add(8); list.add(1); //print the original list System.out.println("Original Linked List:"); list.print_Llist(list.head); //sort the list using insertion sort list.insertion_Sort(list.head); //print the sorted list System.out.println("\nSorted Linked List:"); list.print_Llist(list.head); } }

**Output:**

Original Linked List:

1 8 32 2 10

Sorted Linked List:

1 2 8 10 32

In the above program, we have defined a class that creates a linked list and adds nodes to it as well as sorts it. As the singly linked list has a next pointer, it is easier to keep a track of nodes when sorting the list.

### Sorting A Doubly-Linked List Using Insertion Sort

The following program sorts a doubly-linked list using Insertion sort. Note that as the doubly linked list has both previous and next pointers, it is easy to update and relink the pointers while sorting the data.

class Main { // doubly linked list node static class Node { int data; Node prev, next; }; // return a new node in DLL static Node getNode(int data){ //create new node Node newNode = new Node(); // assign data to node newNode.data = data; newNode.prev = newNode.next = null; return newNode; } // insert a node in sorted DLL static Node insert_Sorted(Node head_ref, Node newNode) { Node current; //list is empty if (head_ref == null) head_ref = newNode; // node is inserted at the beginning of the DLL else if ((head_ref).data >= newNode.data) { newNode.next = head_ref; newNode.next.prev = newNode; head_ref = newNode; } else { current = head_ref; // find the node after which new node is to be inserted while (current.next != null && current.next.data < newNode.data) current = current.next; //update the pointers newNode.next = current.next; if (current.next != null) newNode.next.prev = newNode; current.next = newNode; newNode.prev = current; } return head_ref; } // sort a doubly linked list using insertion sort static Node insertion_Sort(Node head_ref) { // sorted doubly linked list - initially empty Node sorted = null; // Traverse the DLL and insert nodes to sorted list Node current = head_ref; while (current != null) { // current.next goes into next Node next = current.next; // set all links to null current.prev = current.next = null; // current goes in sorted DLL sorted=insert_Sorted(sorted, current); // next now becomes current current = next; } // Update head_ref to point to sorted doubly linked list head_ref = sorted; return head_ref; } // function to print the doubly linked list static void print_DLL(Node head) { while (head != null) { System.out.print(head.data + " "); head = head.next; } } // add new node to DLL at the beginning static Node addNode(Node head_ref, int newData){ // create a new node Node newNode = new Node(); // assign data newNode.data = newData; // Make next of new node as head and previous as null newNode.next = (head_ref); newNode.prev = null; // head=>prev points to new node / if ((head_ref) != null) (head_ref).prev = newNode; // move the head to point to the new node / (head_ref) = newNode; return head_ref; } public static void main(String args[]) { // create empty DLL Node head = null; // add nodes to the DLL head=addNode(head, 5); head=addNode(head, 3); head=addNode(head, 7); head=addNode(head, 2); head=addNode(head, 11); head=addNode(head, 1); System.out.println( "Original doubly linked list:"); print_DLL(head); head=insertion_Sort(head); System.out.println("\nSorted Doubly Linked List:"); print_DLL(head); } }

**Output:**

Original doubly linked list:

1 11 2 7 3 5

Sorted Doubly Linked List:

1 2 3 5 7 11

### Frequently Asked Questions

**Q #1) What is Insertion Sort in Java?**

**Answer:** Insertion sort is a simple sorting technique in Java that is efficient for a smaller data set and in place. It is assumed that the first element is always sorted and then each subsequent element is compared to all its previous elements and placed in its proper position.

**Q #2) ****Why is Insertion Sort better?**

**Answer:** Insertion sort is faster for smaller data sets when the other techniques like quick sort add overhead through recursive calls. Insertion sort is comparatively more stable than the other sorting algorithms and requires less memory. Insertion sort also works more efficiently when the array is almost sorted.

**Q #3) ****What is the Insertion Sort used for?**

**Answer:** Insertion sort is mostly used in computer applications that build complex programs like file searching, path-finding, and data compression.

**Q #4) What is the efficiency of Insertion Sort?**

**Answer:** Insertion sort has an Average case performance of O (n^2). The best case for insertion sort is when the array is already sorted and it is O (n). Worst-case performance for insertion sort is again O (n^2).

## Conclusion

Insertion sort is a simple sorting technique that works on Arrays or linked lists. It is useful when the data set is smaller. As the data set gets bigger, this technique becomes slower and inefficient.

The Insertion sort is also more stable and in-place than the other sorting techniques. There is no memory overhead as no separate structure is used for storing sorted elements.

Insertion sort works well on sorting linked lists that are both singly and doubly-linked lists. This is because the linked list is made up of nodes that are connected through pointers. Hence sorting of nodes becomes easier.

**In our upcoming tutorial, we will discuss yet another sorting technique in Java.**

**=> Read Through The Easy Java Training Series.**