Program Code

import java.util.Arrays;

public class InsertionSort {

    /**
     * Sorts an array using the insertion sort algorithm.
     * 
     * @param array The array to be sorted.
     */
    public static void insertionSort(int[] array) {
        for (int i = 1; i < array.length; i++) { int key = array[i]; int j = i - 1; // Move elements of array[0..i-1] that are greater than key // to one position ahead of their current position while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j = j - 1;
            }
            array[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] numbers = {12, 11, 13, 5, 6};
        System.out.println("Original Array: " + Arrays.toString(numbers));
        
        insertionSort(numbers);
        
        System.out.println("Sorted Array: " + Arrays.toString(numbers));
    }
}

Program Structure Explanation

The program consists of a single class called InsertionSort which contains:

• insertionSort(int[] array): A method that implements the insertion sort algorithm.
  This method takes an integer array as input and sorts it in ascending order.
• main(String[] args): The entry point of the program.
  It initializes an example array, calls the insertionSort method, and prints both the original and sorted arrays.

Insertion Sort Algorithm

The insertion sort algorithm builds the final sorted array one item at a time.
It works by dividing the array into a “sorted” and an “unsorted” part. The sorted part grows with each iteration:

1. Start with the first element, as the sorted part.
2. Pick the next element from the unsorted part.
3. Insert this element into the correct position in the sorted part.
4. Repeat until all elements are sorted.

Complexity

The time complexity of the insertion sort algorithm is:

• Best Case: O(n) – When the array is already sorted.
• Average Case: O(n²) – For random order arrays.
• Worst Case: O(n²) – When the array is sorted in reverse order.

The space complexity is O(1) since it is an in-place sorting algorithm.