Insertion Sort in Java

1. Introduction to Insertion Sort

Insertion Sort is a simple and intuitive sorting algorithm. It is widely taught in computer science courses because it demonstrates the basic concept of sorting by comparison and shifting. The algorithm mimics the way we sort playing cards in our hands — by inserting one card at a time into its correct position.

The core idea is to maintain a growing sorted subarray on the left while inserting the next unsorted element into it by shifting the appropriate values.

2. How Insertion Sort Works

Insertion Sort processes the array in the following way:

Start from the second element (index 1), assuming the first element is already sorted.
- The first element of the array (at index 0) doesn’t need sorting since a single element is trivially sorted.
Pick the current element (key) and compare it with elements before it.
- If the key is smaller than any of the elements in the sorted part, shift those elements one position to the right.
Find the correct position for the key by continuing the comparison until you find an element smaller than or equal to the key, or until you reach the beginning of the array.
Insert the key into its correct position in the sorted portion of the array.
Repeat this process for each subsequent element in the array until the entire array is sorted.

This way, each new element gets “inserted” into its correct place, thus the name Insertion Sort.

3. Dry Run Example of Insertion Sort

Let’s sort this array:

Initial Array: [5, 2, 4, 6, 1, 3]

Iteration 1 (i = 1, key = 2):

Compare with 5 → 5 > 2 → shift 5 one position right.
No more elements to compare.
Insert 2 at index 0.
Result: [2, 5, 4, 6, 1, 3]

Iteration 2 (i = 2, key = 4):

Compare with 5 → 5 > 4 → shift 5.
Compare with 2 → 2 < 4 → stop.
Insert 4 at index 1.
Result: [2, 4, 5, 6, 1, 3]

Iteration 3 (i = 3, key = 6):

Compare with 5 → 5 < 6 → stop.
Insert 6 at index 3 (no change).
Result: [2, 4, 5, 6, 1, 3]

Iteration 4 (i = 4, key = 1):

Compare with 6, 5, 4, 2 → all are greater → shift all.
Insert 1 at index 0.
Result: [1, 2, 4, 5, 6, 3]

Iteration 5 (i = 5, key = 3):

Compare with 6, 5, 4 → all greater → shift all.
Compare with 2 → 2 < 3 → stop.
Insert 3 at index 2.
Result: [1, 2, 3, 4, 5, 6]

4. Java Implementation of Insertion Sort

public class InsertionSort {

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

        // Traverse from index 1 to n-1
        for (int i = 1; i < n; i++) {
            int key = arr[i];  // Element to be inserted into the sorted part
            int j = i - 1;

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

            // Place the key at its correct position
            arr[j + 1] = key;
        }
    }

    // Utility method to print an array
    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    // Main method to test the sorting
    public static void main(String[] args) {
        int[] array = {5, 2, 4, 6, 1, 3};

        System.out.println("Original Array:");
        printArray(array);

        insertionSort(array);

        System.out.println("Sorted Array:");
        printArray(array);
    }
}

4.1 Explaination of code

for (int i = 1; i < n; i++) {

We loop from the second element (index 1) to the last element.
We start from index 1 because a single element (at index 0) is already sorted.

int key = arr[i];

The key is the current element that we want to insert into the correct position within the sorted subarray on the left.
Example: if i = 2 and array is [2, 4, 5, ...], then key = 5.

int j = i - 1;

j starts from the element just before the key.
We use j to compare the key with previous (sorted) elements.

while (j >= 0 && arr[j] > key) {
    arr[j + 1] = arr[j];
    j--;
}

This loop checks if the current element (arr[j]) is greater than the key.
If so, it shifts arr[j] one position to the right (to arr[j + 1]).
j-- moves to the previous element for further comparison.
This continues until we find the right position for key.

arr[j + 1] = key;

After finding the right place, we insert the key at that position.
Why j + 1? Because in the last iteration of the loop, j was decremented one extra time.

5. Time and Space Complexity Analysis

Scenario	Complexity	Explanation
Best Case	O(n)	When the array is already sorted; only one comparison per element is required.
Average Case	O(n²)	On average, each element needs to be compared with half of the sorted array.
Worst Case	O(n²)	When the array is sorted in reverse order; each element needs to be compared with and shifted past all previously sorted elements.

6. When Should You Use Insertion Sort?

Although Insertion Sort is not suitable for large datasets due to its O(n²) time complexity, it is very useful in certain scenarios:

For small datasets: Insertion Sort performs better than more complex algorithms like QuickSort for small arrays (e.g., less than 20 elements).
When the data is nearly sorted: If the array is already partially sorted, Insertion Sort can run in almost linear time.
When stability is required: Insertion Sort maintains the relative order of equal elements, which is critical for certain applications.
In online systems: It can sort a list as it receives elements (online algorithm).
Educational purposes: It is easy to implement and understand, making it ideal for teaching sorting fundamentals.

7. Pros and Cons of Insertion Sort

Pros:

Simple and easy to implement: Ideal for beginners and small projects.
Efficient for small or partially sorted arrays.
Stable sorting: Preserves the relative order of records with equal keys.
In-place sort: No extra memory required.

Cons:

Inefficient for large arrays: Due to its O(n²) time complexity.
Many unnecessary comparisons and shifts when data is unordered.

8. Visual representation

Initial State:

[5 | 2, 4, 6, 1, 3]
      ^
Key = 2

Compare 2 with 5 → shift 5 right.

[5, 5 | 4, 6, 1, 3]
      ^
Insert 2 at index 0

Result: [2, 5 | 4, 6, 1, 3]

Iteration 2 (i = 2):

[2, 5 | 4, 6, 1, 3]
           ^
Key = 4

Compare 4 with 5 → shift 5
Compare 4 with 2 → 2 < 4 → stop.

[2, 5, 5 | 6, 1, 3]
           ^
Insert 4 at index 1

Result: [2, 4, 5 | 6, 1, 3]

Iteration 3 (i = 3):

[2, 4, 5 | 6, 1, 3]
              ^
Key = 6

6 > 5 → no shifts needed.

Insert 6 at index 3 (already there)

Result:

[2, 4, 5, 6 | 1, 3]

Iteration 4 (i = 4):

[2, 4, 5, 6 | 1, 3]
                 ^
Key = 1

Compare 1 with 6 → shift
Compare with 5 → shift
Compare with 4 → shift
Compare with 2 → shift
Insert 1 at index 0

[2, 4, 5, 6, 6 | 3]
                 ^
→ [2, 4, 5, 5, 6 | 3]  
→ [2, 4, 4, 5, 6 | 3]  
→ [2, 2, 4, 5, 6 | 3]  
Insert 1 at index 0

Result: [1, 2, 4, 5, 6 | 3]

Iteration 5 (i = 5):

[1, 2, 4, 5, 6 | 3]
                    ^
Key = 3

Compare 3 with 6 → shift
Compare with 5 → shift
Compare with 4 → shift
Compare with 2 → stop

[1, 2, 4, 5, 6, 6]
→ [1, 2, 4, 5, 5, 6]
→ [1, 2, 4, 4, 5, 6]
Insert 3 at index 2

Final Sorted Array:
[1, 2, 3, 4, 5, 6]