Insertion Sort

The insertion-sort algorithm sorts a list of values by repeatedly inserting a new element into a sorted sublist until the whole list is sorted. Figure below shows how to sort the list {2, 9, 5, 4, 8, 1, 6} using insertion sort.

The algorithm can be described as follows:

for (int i = 1; i < list.length; i++) {
insert list[i] into a sorted sublist list[0..i-1] so that
list[0..i] is sorted.
}

To insert list[i] into list[0..i-1], save list[i] into a temporary variable, say currentElement. Move list[i-1] to list[i] if list[i-1] > currentElement, move list[i-2] to list[i-1] if list[i-2] > currentElement, and so on, until list[i-k] <= currentElement or k > i (we pass the first element of the sorted list). Assign currentElement to list[i-k+1]. For example, to insert 4 into {2, 5, 9} in Step 4 in Figure below, move list[2] (9) to list[3] since 9 > 4, and move list[1] (5) to list[2] since 5 > 4. Finally, move currentElement (4) to list[1].

The algorithm can be expanded and implemented as in code below:

The insertionSort(int[] list) method sorts any array of int elements. The method is implemented with a nested for loop. The outer loop (with the loop control variable i) (line 4) is iterated in order to obtain a sorted sublist, which ranges from list[0] to list[i]. The inner loop (with the loop control variable k) inserts list[i] into the sublist from list[0] to list[i-1].

To better understand this method, trace it with the following statements:

int[] list = {1, 9, 4, 6, 5, -4};
InsertionSort.insertionSort(list);

The insertion sort algorithm presented here sorts a list of elements by repeatedly inserting a new element into a sorted partial array until the whole array is sorted. At the kth iteration, to insert an element into an array of size k, it may take k comparisons to find the insertion position, and k moves to insert the element. Let T(n) denote the complexity for insertion sort and c denote the total number of other operations such as assignments and additional comparisons in each iteration. Thus,

Therefore, the complexity of the insertion sort algorithm is O(n^2). Hence, the selection sort and insertion sort are of the same time complexity.