Java Programs for Sorting Algorithms

Insertion Sort

Insertion Sort is a simple sorting algorithm similar to Bubble Sort and Selection Sort. It has more advantages compare to Bubble Sort or Insertion Sort.

Advantages of Insertion Sort.

• Efficient algorithm for small dataset.Also better than other O(n²) algorithms
• Constant space complexity

How Insertion Sort Works

In each iteration, the algorithm removes one element from the input list and find the location of the element in the sorted list and inserts it there.

How Insertion Sort works

Iterative Method

public void insertionSortIterative(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int key = array[i];
        int j = i - 1;
        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
}

Recursive Method

public void insertionSortRecursive(int[] array, int n) {
    if (n < 1) {
        return;
    }
    insertionSortRecursive(array, n - 1);
    int key = array[n];
    int j = n - 1;
    while (j >= 0 && array[j] > key) {
        array[j + 1] = array[j];
        j--;
    }
    array[j + 1] = key;
}