Insertion Sort

Insertion Sort is a simple sorting algorithm that works like sorting a hand of playing cards. The algorithm iterates over the array and checks if each element is less than the previous one. In that case, iterate through the sorted portion of the array to find the correct position of the element and insert it there.

Insertion sort takes each element and places it in its correct position.

Example

Given an unsorted integer array of size 6.

Pass1: Take 13 and place it in its correct position

Pass2: Take 24 and place it in its correct position

Pass3: Take 46 and place it in its correct position

Pass4: Take 20 and place it in its correct position

Pass5: Take 9 and place it in its correct position

Pass6: Take 52 and place it in its correct position

We have the sorted array after Pass 5.

Approach

1. Get the length of the array using arr.length and assign it to the variable n.
2. Start a loop that goes from i = 1 to i < n. This loop iterates over the array, starting from the second element, since the first element is considered to be sorted.
3. Assign the current element to the variable key.
4. Start a while loop that goes from j = i-1 to j >= 0 and check if the element at arr[j] is greater than the key.
5. If the condition in step 4 is true, we move the element at arr[j] one position to the right and decrement j.
6. Continue step 4 and 5 until we find the correct position for the key.
7. Insert the key at the correct position in the sorted sublist.

Complexity

• Time Complexity: Worst case is O(n^2), where n is the size of the array, average case is O(n^2) too. In best case it can be O(n).
• Space Complexity: O(1)

Code

# Java Code

import java.util.Arrays;

public class InsertionSort {

    public static void insertionSort(int[] array) {
        int length = array.length;
        for (int currentIndex = 1; currentIndex < length; currentIndex++) {
            int currentValue = array[currentIndex];
            int previousIndex = currentIndex - 1;
            while (previousIndex >= 0 && array[previousIndex] > currentValue) {
                array[previousIndex + 1] = array[previousIndex];
                previousIndex--;
            }
            array[previousIndex + 1] = currentValue;
        }
    }

    public static void main(String[] args) {
        int[] array = { 13, 46, 24, 52, 20, 9 };
        System.out.println("Original array: " + Arrays.toString(array));
        insertionSort(array);
        System.out.println("Sorted array: " + Arrays.toString(array));
    }
}

Output

Original array : [13, 46, 24, 52, 20, 9]

Sorted array : [9, 13, 20, 24, 46, 52]