Insertion Sort

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages in certain scenarios. It has an average and worst-case time complexity of O(n^2).

Algorithm

The algorithm works by dividing the input array into a sorted subarray and an unsorted subarray. At each iteration, the next element in the unsorted subarray is picked and inserted into its correct position in the sorted subarray. This process continues until the entire array is sorted.

Steps of Insertion Sort

1. Iterate from arr[1] to arr[n], where n is the length of the array.
2. Compare the current element (key) with the element in the sorted subarray on the left.
3. If the current element is smaller, shift the element to the right.
4. Repeat step 3 until the correct position for the key is found.
5. Insert the key into its correct position in the sorted subarray.

Example

Let's see an implementation of Insertion Sort in Java:

1${code}

xxxxxxxxxx

import java.util.Arrays;

​

public class InsertionSort {

​

    public static void insertionSort(int[] arr) {

        int n = arr.length;

        for (int i = 1; i < n; ++i) {

            int key = arr[i];

            int j = i - 1;

​

            while (j >= 0 && arr[j] > key) {

                arr[j + 1] = arr[j];

                j = j - 1;

            }

            arr[j + 1] = key;

        }

    }

​

    public static void main(String[] args) {

        int[] arr = {64, 34, 25, 12, 22, 11, 90};

        insertionSort(arr);

        System.out.println("Sorted array: " + Arrays.toString(arr));

    }

}