Insertion sort in Java

Remember, Insertion sort is a simple sorting algorithm that performs an in-place sorting. It divides the array into sorted and unsorted parts. Each iteration, the algorithm moves an element from the unsorted part to sorted one until all the elements are sorted in the array. The moving element is inserted in a suitable position in the sorted part.

The algorithm is stable, i.e. it doesn't change the relative order of identical elements.

The Java implementation

In the following code, the insertion sort algorithm implemented as a static method. It has two loops. In the outer loop, it takes the next element, and in the nested loop, it moves the element to the sorted part keeping the order.

public static int[] insertionSort(int[] array) {

    /* iterating over elements in the unsorted part */    
    for (int i = 1; i < array.length; i++) {        
        int elem = array[i]; // take the next element
        int j = i - 1;
            
        /* find a suitable position to insert and shift elements to the right */
        while (j >= 0 && array[j] > elem) {
            array[j + 1] = array[j]; // shifting
            j--;
        }
        array[j + 1] = elem; // insert the element in the found position in the sorted part
    }
        
    return array;
}

Let's test the method passing different arrays.

insertionSort(new int[] { 21, 23, 19, 30, 11, 28 }); // { 11, 19, 21, 23, 28, 30 }
insertionSort(new int[] { 30, 28, 23, 21, 19, 11 }); // { 11, 19, 21, 23, 28, 30 }