Insertion Sort Example Java Program


Definition

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) 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 like simple implementation, efficient for (quite) small data sets, more efficient in practice than most other simple quadratic algorithms, adaptive, stable, in-place; i.e., only requires a constant amount of additional memory space, online; i.e., can sort a list as it receives it

Insertion Sort Example Program

import java.util.Arrays;
 
public class InsertionSort {
    public static void main(String[] args) {
        int arr1[] = new int[10];
        populateArray(arr1);
        System.out.println("Numbers to be sorted: ");
        printArray(arr1);
        insertionSort(arr1);
        System.out.println("\nAfter Sorting: ");
        printArray(arr1);
    }
    private static void insertionSort(int[] arr2) {
        for (int i = 1; i < arr2.length; i++) {
            int sort = arr2[i];
            int j = i;
            while (j > 0 && arr2[j - 1] > sort) {
                arr2[j] = arr2[j - 1];
                j--;
            }
            arr2[j] = sort;
        }
    }
    public static void printArray(int[] arr3) {
        System.out.println(Arrays.toString(arr3));
    }
    public static void populateArray(int[] arr3) {
        for (int i = 0; i < arr3.length; i++) {
            arr3[i] = (int) (Math.random() * 100);
        }
    }
}

Sample Output

Output is:
Numbers to be sorted:
[29, 6, 25, 7, 15, 86, 48, 78, 29, 4]

After Sorting:
[4, 6, 7, 15, 25, 29, 29, 48, 78, 86]