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.

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;

}