InsertionSort

Insertion Sort is an efficient algorithm for ordering a small number of items. The algorithm is as follows:

The index_i_indicates the position of the current item in the array to process.

We begin from the second item as by definition an array with one item is considered to be sorted. The item at index i_is called a_key. Once having the key, the second part of the algorithm deals with finding its correct index.If the key is smaller than the value of the item at index j, then the key moves one position to the left.The process continues until the case when we reach an element being smaller than the key.

It's important to note that before starting the iteration for finding the correct position of thekey_at index _i, the arrayA[1 .. j – 1]_is already_sorted.

In detail, At any given time during the iteration,we could think of this array as being logically divided into two portions;the left side being the sorted one and right side containing the items not yet sorted. An important note here is that after finding the correct position at which we'll insert the new item,we shift (and not swap) the items to the rightto free a space for it.

    public static void insertSort(int[] nums) {
        if (nums == null) return;

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

The time taken by the INSERTION-SORTprocedure to run isO(n^2). For each new item, we iterate from right to left over the already sorted portion of the array to find its correct position. Then we insert it by shifting the items one position to the right.

The algorithm sorts in place so its space complexity is O(1) for the imperative implementation and O(n) for the recursive implementation.