Insertion Sort in Java

Insertion Sort is a simple and efficient comparison-based sorting algorithm that works similarly to how you might sort playing cards in your hands. It builds the sorted array one element at a time by placing each new element into its correct position within the already sorted part of the array.

Insertion Sort Algorithm Steps:

1. Assume the first element is already sorted.
2. Start with the second element (i = 1) and compare it to the elements in the sorted portion of the array (from i-1 to 0).
3. Shift all elements greater than the current element one position to the right to make space for it.
4. Insert the current element into its correct position.
5. Repeat this process for all elements until the entire array is sorted.

Understand it with an Example:

Input Array: [12, 11, 13, 5, 6]

1. Initial Array: [12, 11, 13, 5, 6]
2. Pass 1 (i = 1):
   • Key = 11, compare with 12 (sorted part).
   • Shift 12 to the right: [12, 12, 13, 5, 6]
   • Insert 11: [11, 12, 13, 5, 6].
3. Pass 2 (i = 2):
   • Key = 13, compare with 12.
   • No shift needed, insert 13: [11, 12, 13, 5, 6].
4. Pass 3 (i = 3):
   • Key = 5, compare with 13, 12, and 11.
   • Shift 13, 12, and 11 to the right: [11, 11, 12, 13, 6]
   • Insert 5: [5, 11, 12, 13, 6].
5. Pass 4 (i = 4):
   • Key = 6, compare with 13, 12, and 11.
   • Shift 13, 12, and 11 to the right: [5, 6, 11, 12, 13]
   • Insert 6: [5, 6, 11, 12, 13].

Output: [5, 6, 11, 12, 13]

package com.javacodepoint.sort;

public class InsertionSort {

	// Method to perform insertion sort
	public static void insertionSort(int[] array) {
		int n = array.length;

		// Traverse the array from the second element
		for (int i = 1; i < n; i++) {
			int key = array[i];
			int j = i - 1;

			// Shift elements of the sorted part to the right to make space for the key
			while (j >= 0 && array[j] > key) {
				array[j + 1] = array[j];
				j--;
			}

			// Place the key in its correct position
			array[j + 1] = key;
		}
	}

	public static void main(String[] args) {
		// Example input array
		int[] numbers = { 12, 11, 13, 5, 6 };

		// Print the original array
		System.out.println("Original Array:");
		for (int num : numbers) {
			System.out.print(num + " ");
		}

		// Perform insertion sort
		insertionSort(numbers);

		// Print the sorted array
		System.out.println("\nSorted Array:");
		for (int num : numbers) {
			System.out.print(num + " ");
		}
	}
}

OUTPUT:

Original Array:
12 11 13 5 6
Sorted Array:
5 6 11 12 13

Time Complexity:

• Best Case (nearly sorted array): O(n)
• Average Case: O(n^2)
• Worst Case (reverse sorted array): O(n^2)

Space Complexity:

• Space: O(1) (in-place sorting).