insertion sort

Insertion Sort:

Insertion Sort is a simple, comparison-based sorting algorithm that builds the final sorted array one element at a time. It works by dividing the array into a “sorted” and “unsorted” section. The sorted section is built from left to right, and each new element is inserted into its correct position in the sorted section.

How Insertion Sort Works:

  1. Assume the first element is already sorted.
  2. Take the next element and compare it with elements in the sorted section, moving it left until it is in the correct position.
  3. Repeat for all elements in the unsorted section.

Time Complexity:

  • Worst-case and average-case time complexity: O(n²) (when the array is in reverse order).
  • Best-case time complexity: O(n) (when the array is already sorted).
import java.util.Arrays;

public class InsertionSort {

    // Function to implement insertion sort
    public static void insertionSort(int[] arr) {
        int n = arr.length;

        // Start from the second element since the first is "already sorted"
        for (int i = 1; i < n; i++) {
            int key = arr[i];  // Element to be inserted into the sorted part
            int j = i - 1;

            // Move elements that are greater than 'key' one position to the right
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];  // Shift element to the right
                j--;
            }

            // Insert 'key' into its correct position
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};

        System.out.println("Original array: " + Arrays.toString(arr));

        // Perform insertion sort
        insertionSort(arr);

        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

Explanation:

  • Outer Loop: Iterates through the array starting from the second element, because the first element is already considered “sorted.”
  • Inner Loop: Compares the current element (key) with elements in the sorted section. If the current element is smaller, it shifts the larger elements to the right.
  • Key: The key is inserted into the correct position in the sorted section after shifting.

How It Works:

  • In the first pass, the second element is compared to the first. If the second element is smaller, it is inserted before the first element.
  • In the next pass, the third element is compared to the elements in the sorted section (first and second elements). It is inserted into its correct position.
  • The process continues until all elements are sorted.

Key Points:

  • Insertion Sort is efficient for small datasets or nearly sorted arrays.
  • It has a time complexity of O(n²) in the worst and average cases, but O(n) in the best case when the array is already sorted.
  • It is a stable sorting algorithm, meaning it maintains the relative order of elements with equal values.
  • It can be more efficient than selection or bubble sort for small or nearly sorted arrays.
© 2025 GeeksDirectory