### DS and Algorithms in Java

In this article, we will discuss what is insertion sort, how it works? and how to implement it using Java.

## What is Insertion Sort Algorithm?

Insertion sort is a simple and efficient comparison sort. In this algorithm, each iteration removes an element from the input data and inserts it into the correct position in the list is sorted. The choice of the element is removed from the input is random and this process is repeated until all input elements have gone through.

• Efficient for small data
• Adaptive: If the input list is presorted [may not be complete] then insertions sort takes O(n + d), where d is the number of inversions
• Practically more efficient than selection and bubble sorts, even though all of them have O(n2) worst case complexity
• Stable: Maintains relative order of input data if the keys are same
• In-place: It requires only a constant amount O(1) of additional memory space
• Online: Insertion sort can sort the list as it receives it

### How Insertion Sort Works?

Let's understand how insertion sort works with a simple example.
Step 1: Let's we have input as integer array:
``````12, 11, 13, 5, 6
``````
Let us loop for i = 1 (second element of the array) to 5 (Size of input array)
Step 2: For i = 1, since 11 is smaller than 12, move 12 and insert 11 before 12
``````11, 12, 13, 5, 6
``````
Step 3: For i = 2, 13 will remain at its position as all elements in A[0..i-1] are smaller than 13
``````11, 12, 13, 5, 6
``````
Step 4: For i = 3, 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.
``````5, 11, 12, 13, 6
``````
Step 5: For i = 4, 6 will move to a position after 5, and elements from 11 to 13 will move one position ahead of their current position.
``````5, 6, 11, 12, 13
``````
Let's look at the source so that we can understand this flow easily.

## Insertion Sort Implementation in Java

```import java.util.Arrays;

/**
* Class demonstrate the Insertion sort algorithm
*
*/

public class InsertionSort {
/* Function to sort array using insertion sort */
private void insertionSort(int arr[]) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;

/*
* Move elements of arr[0..i-1], that are greater than key, to one
* position ahead of their current position
*/
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

public static void main(String args[]) {
InsertionSort insertionSort = new InsertionSort();
int arr[] = { 20, 10, 5, 6, 2, 3, 4 };

System.out.println("Before Sorting an array : " + Arrays.toString(arr));
insertionSort.insertionSort(arr);
System.out.println("After Sorting an array : " + Arrays.toString(arr));
}
}```
Output:
``````Before Sorting an array : [20, 10, 5, 6, 2, 3, 4]
After Sorting an array : [2, 3, 4, 5, 6, 10, 20]``````

## Generic Implementation

Let's create a generic implementation of the Insertion Sort algorithm so that we can sorting Integer, String, Double etc. Sorts according to the natural ordering of its elements. Wrapper classes and String internally implement the Comparable interface.
This program demonstrates sorting Integer and String array using Insertion Sort Algorithm.
```import java.util.Arrays;

/**
* Insertion sort is a simple sorting algorithm: a comparison sort in which the
* sorted array (or list) is built one entry at a time. It is much less
* efficient on large lists than more advanced algorithms such as quicksort,
* heapsort, or merge sort.
*
*/
public class InsertionSort<T extends Comparable<T>> {

private InsertionSort() {
}

public static <T extends Comparable<T>> T[] sort(T[] unsorted) {
int length = unsorted.length;
for (int i = 1; i < length; i++) {
sort(i, unsorted);
}
return unsorted;
}

private static <T extends Comparable<T>> void sort(int i, T[] unsorted) {
for (int j = i; j > 0; j--) {
T jthElement = unsorted[j];
T jMinusOneElement = unsorted[j - 1];
if (jthElement.compareTo(jMinusOneElement) < 0) {
unsorted[j - 1] = jthElement;
unsorted[j] = jMinusOneElement;
} else {
break;
}
}
}

public static void main(String[] args) {
Integer arr[] = { 20, 10, 5, 6, 2, 3, 4 };

System.out.println("--------Sorting integer array using insertion sort algorithm--------");
System.out.println();
System.out.println("Before Sorting an array : " + Arrays.toString(arr));
InsertionSort.sort(arr);
System.out.println("After Sorting an array : " + Arrays.toString(arr));

System.out.println();
System.out.println("--------Sorting String array using insertion sort algorithm--------");
System.out.println();

String[] stringArray = { "c", "a", "e", "b", "d" };
System.out.println("Before sorting the array elements : " + Arrays.toString(stringArray));
InsertionSort.sort(stringArray);
System.out.println("After sorting the array elements : " + Arrays.toString(stringArray));

}
}```
Output:
``````--------Sorting integer array using insertion sort algorithm--------

Before Sorting an array : [20, 10, 5, 6, 2, 3, 4]
After Sorting an array : [2, 3, 4, 5, 6, 10, 20]

--------Sorting String array using insertion sort algorithm--------

Before sorting the array elements : [c, a, e, b, d]
After sorting the array elements : [a, b, c, d, e]``````

## Performance

If every element is greater than or equal to every element to its left, the running time of insertion sort is Θ(n). This situation occurs if the array starts out already sorted, and so an already-sorted array is the best case for insertion sort.
1. Worst case complexity: Θ(n2)
2. Best case complexity: Θ(n)
3. Average case complexity: Θ(n2)
4. Worst case space complexity: O(n2) total, O(1) auxiliary