Insertion Sort

I. Concept and Introduction

Insertion Sort, commonly known as direct insertion sort, is an effective algorithm for sorting a small number of elements. The basic idea of insertion sort is to insert a record into an already sorted list, resulting in a new list with one additional record. The implementation uses a double-layer loop: the outer loop iterates over all elements except the first, and the inner loop searches for the correct insertion position in the sorted list before the current element and performs the necessary shifts.

II. Applicability

The average time complexity of insertion sort is also O(n^2), with a space complexity of constant order O(1). The actual time complexity is also related to the orderliness of the array. In the best case scenario where the array is already sorted, only N-1 comparisons are needed, resulting in a time complexity of O(N). The worst case occurs when the array is in reverse order, requiring the maximum number of comparisons, which is O(n^2).

III. Process Illustration

Suppose the first n-1 (where n>=2) elements are already sorted. Now, the n-th element is inserted into the previously sorted sequence, finding its appropriate position to maintain the sorted order. This process is repeated for all elements until the entire sequence becomes sorted.

The entire process of insertion sort from smallest to largest is illustrated as follows:

First Round: Starting from the second position, 6 is compared with the previous 7, and they swap positions.

Second Round: The third position's 9 is compared with the previous 7, no swap is needed.

Third Round: The fourth position's 3 is compared with the previous 9, swapping positions and continuing to compare backwards.

Fourth Round: The fifth position's 1 is compared with the previous 9, swapping positions and continuing to compare backwards.

...

This process continues until the last element.

IV. Java Example Code

Source Code Download: Download

Partial Code:

InsertionSort.java File Code:

package tutorialpro;

/**
 * Insertion Sort
 */
public class InsertionSort {
    // Core code---start
    public static void sort(Comparable[] arr){

        int n = arr.length;
        for (int i = 0; i < n; i++) {
            // Find the correct insertion position for element arr[i]
            for( int j = i ; j > 0 ; j -- )
                if( arr[j].compareTo( arr[j-1] ) < 0 )
                    swap( arr, j , j-1 );
                else
                    break;
        }
    }
    // Core code---end
    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {

        int N = 20000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        InsertionSort.sort(arr);
        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(' ');
        }
    }
}