Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Basic Insertion Sort

Problem Statement

Write a Java program that implements the Insertion Sort algorithm to sort an array of integers in ascending order. The program should count the number of shifts performed (the number of times elements are moved to make space for insertion) and test the implementation with various input arrays, including unsorted, already sorted, reversed, and arrays with duplicate elements. Insertion Sort builds a sorted portion of the array from the start, inserting each new element into its correct position by shifting larger elements. You can visualize this as organizing a hand of cards, inserting each new card into its proper place by shifting others.

Input:

  • An array of integers to be sorted. Output: The sorted array, the number of shifts performed, and a string representation of the input and sorted arrays for clarity. Constraints:
  • The array length n is between 0 and 10^5.
  • Array elements are integers in the range [-10^9, 10^9]. Example:
  • Input: array = [64, 34, 25, 12, 22]
  • Output:
    • Input Array: [64, 34, 25, 12, 22]
    • Sorted Array: [12, 22, 25, 34, 64]
    • Shifts: 10
  • Explanation: Insertion Sort inserts each element, shifting larger ones, resulting in 10 shifts.
  • Input: array = [1, 2, 3]
  • Output:
    • Input Array: [1, 2, 3]
    • Sorted Array: [1, 2, 3]
    • Shifts: 0
  • Explanation: Already sorted array requires no shifts.

Pseudocode

FUNCTION insertionSort(arr)
    SET n to length of arr
    CREATE shifts as integer, initialized to 0
    FOR i from 1 to n-1
        SET key to arr[i]
        SET j to i - 1
        WHILE j >= 0 AND arr[j] > key
            SET arr[j + 1] to arr[j]
            INCREMENT shifts
            DECREMENT j
        ENDWHILE
        SET arr[j + 1] to key
    ENDFOR
    RETURN shifts
ENDFUNCTION

FUNCTION toString(arr)
    CREATE result as new StringBuilder
    APPEND "[" to result
    FOR each element in arr
        APPEND element to result
        IF element is not last THEN
            APPEND ", " to result
        ENDIF
    ENDFOR
    APPEND "]" to result
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of input arrays
    FOR each testCase in testCases
        PRINT test case details
        CREATE copy of testCase array
        SET shifts to insertionSort(copy)
        PRINT input array, sorted array, and shifts
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define insertionSort: a. Initialize a counter shifts to 0. b. For each index i from 1 to n-1:
    • Store arr[i] as key.
    • Shift elements arr[j] (j from i-1 down to 0) that are greater than key one position forward, incrementing shifts for each move.
    • Insert key at the correct position. c. Return the number of shifts.
  2. Define toString: a. Convert the array to a string, e.g., "[64, 34, 25, 12, 22]".
  3. In main, test with: a. An unsorted array. b. An already sorted array. c. A reversed array. d. An array with duplicates. e. An empty array.

Java Implementation

import java.util.*;

public class BasicInsertionSort {
    // Performs Insertion Sort and counts shifts
    public int insertionSort(int[] arr) {
        int n = arr.length;
        int shifts = 0;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                shifts++;
                j--;
            }
            arr[j + 1] = key;
        }
        return shifts;
    }

    // Converts array to string
    public String toString(int[] arr) {
        StringBuilder result = new StringBuilder("[");
        for (int i = 0; i < arr.length; i++) {
            result.append(arr[i]);
            if (i < arr.length - 1) {
                result.append(", ");
            }
        }
        result.append("]");
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        int[] arr;
        String description;

        TestCase(int[] arr, String description) {
            this.arr = arr;
            this.description = description;
        }
    }

    // Main method to test Insertion Sort
    public static void main(String[] args) {
        BasicInsertionSort sorter = new BasicInsertionSort();

        // Test cases
        TestCase[] testCases = {
            new TestCase(new int[]{64, 34, 25, 12, 22}, "Unsorted"),
            new TestCase(new int[]{1, 2, 3, 4, 5}, "Sorted"),
            new TestCase(new int[]{5, 4, 3, 2, 1}, "Reversed"),
            new TestCase(new int[]{3, 1, 3, 2, 1}, "Duplicates"),
            new TestCase(new int[]{}, "Empty")
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            System.out.println("Test case " + (i + 1) + ": " + testCases[i].description);
            int[] arr = testCases[i].arr.clone(); // Copy to preserve original
            System.out.println("Input Array: " + sorter.toString(arr));
            int shifts = sorter.insertionSort(arr);
            System.out.println("Sorted Array: " + sorter.toString(arr));
            System.out.println("Shifts: " + shifts + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1: Unsorted
Input Array: [64, 34, 25, 12, 22]
Sorted Array: [12, 22, 25, 34, 64]
Shifts: 10

Test case 2: Sorted
Input Array: [1, 2, 3, 4, 5]
Sorted Array: [1, 2, 3, 4, 5]
Shifts: 0

Test case 3: Reversed
Input Array: [5, 4, 3, 2, 1]
Sorted Array: [1, 2, 3, 4, 5]
Shifts: 10

Test case 4: Duplicates
Input Array: [3, 1, 3, 2, 1]
Sorted Array: [1, 1, 2, 3, 3]
Shifts: 5

Test case 5: Empty
Input Array: []
Sorted Array: []
Shifts: 0

Explanation:

  • Test case 1: Unsorted array requires 10 shifts to sort.
  • Test case 2: Already sorted array requires 0 shifts.
  • Test case 3: Reversed array requires 10 shifts (worst case).
  • Test case 4: Array with duplicates requires 5 shifts.
  • Test case 5: Empty array requires 0 shifts.

How It Works

  • insertionSort:
    • Iterates from index 1 to n-1, treating arr[0..i-1] as sorted.
    • For each element (key), shifts larger elements in the sorted portion one position forward, counting each shift.
    • Inserts the key in the correct position.
  • toString: Formats array as a string for output.
  • Example Trace (Test case 1):
    • i=1: key=34, shift 64: [34, 64, 25, 12, 22] (1 shift).
    • i=2: key=25, shift 64, 34: [25, 34, 64, 12, 22] (2 shifts).
    • i=3: key=12, shift 64, 34, 25: [12, 25, 34, 64, 22] (3 shifts).
    • i=4: key=22, shift 64, 34, 25: [12, 22, 25, 34, 64] (4 shifts).
    • Total shifts: 10.
  • Main Method: Tests unsorted, sorted, reversed, duplicates, and empty arrays.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
insertionSortO(n²) worst, O(n) bestO(1)
toStringO(n)O(n)

Note:

  • n is the array length.
  • Time complexity: O(n²) for insertionSort in worst/average cases (reversed or random); O(n) in best case (sorted); O(n) for toString.
  • Space complexity: O(1) for insertionSort (in-place); O(n) for toString (string builder).
  • Shifts depend on input order, with fewer shifts for nearly sorted arrays.

✅ Tip: Insertion Sort is efficient for small or nearly sorted arrays due to fewer shifts in the best case. Count shifts instead of swaps to accurately measure its work.

⚠ Warning: Ensure the array is copied before sorting to preserve the original for display. Handle empty arrays to avoid index issues in the sorting loop.