**Insertion sort** is a simple sorting algorithm that allows for efficient, in-place sorting of the array, one element at a time. By in-place sorting, we mean that the original array is modified and no temporary structures are needed. 

We will learn how to implement this style of sorting in Java.

>**Note:** Need to review of the algorithm? [click here.](https://www.educative.io/courses/visual-introduction-to-algorithms/insertion-sort)

# Visualizing the sorting

Now that you remember how Insertion sort works, let's see a small illustration on Insertion sort and how it works on a given array.

# Implementation

Now that we have seen how insertion sort works let's use the example above and write a code that performs this sort.

Change the values of `arr` to see how it works on different arrays.

class insertionSort {

    public static void sortInsertion(int [] sort_arr){

      for(int i=0;i<sort_arr.length;++i){

        int j = i;
        
        while(j > 0 && sort_arr[j-1]>sort_arr[j]){

          int key = sort_arr[j];
          sort_arr[j] = sort_arr[j-1];
          sort_arr[j-1] = key;
          j = j-1; 

        }
      }
    }

    public static void main( String args[] ) {
        int [] arr = {5,2,12,12,1};
        sortInsertion(arr);

        for(int i=0;i<arr.length;++i){
          System.out.print(arr[i] + " ");
        }
    }
}

# Understanding Implementation

* The first step is to create a method that takes in input the array to be sorted, `sort_arr` as seen in *line 3* in the code above.

* The second step is to create an outer `for loop` which will iterate over each element of the array as shown in *line 5*.

* The third step is to create a separate iterator, `j` which will check for the ascending order of elements in the list, as shown in *line 7*.

* The fourth step is the inner `while loop`:
  * As shown in *line 9* the while loop must satisfy two conditions: the value of `j` must be greater than 0, and the value at index `j-1`, must be greater than the value at index `j`.
  * If this condition holds *true* then, as shown from *lines 11 to 14*, the `key` is set to the value at index `j`.
  * Then the values at `j` and `j-1` are swapped.
  * The value of `j` is reduced by 1 and the loop continues till one of the conditions breaks.
* This continues for every iteration of the outer `for loop` till that also breaks.

## Time Complexity

As there are two loops, with the `while` loop nested in the `for loop` the complexity of this algorithm is *`O(n^2)`* where *n* is equal to the length of the array to be sorted.

What is insertion sort in Java?

Insertion sort is an efficient, in-place sorting algorithm in Java with a time complexity of O(n²).