Insertion Sort Algorithm in DSA Java

Mental Model

Insertion sort builds a sorted list by taking one item at a time and placing it in the right spot among the items already sorted.

Analogy: Imagine sorting playing cards in your hand by picking one card and inserting it into the correct position among the cards you already hold sorted.

Unsorted array: [5, 3, 8, 4, 2]
Sorted part ↑
[5] [3] [8] [4] [2]
Initially, only first element is sorted.

Dry Run Walkthrough

Input: array: [5, 3, 8, 4, 2]

Goal: Sort the array in ascending order using insertion sort

Step 1: Take element 3 and compare with 5, shift 5 right

[5, 5, 8, 4, 2] with 3 to insert at index 0

Why: 3 is smaller than 5, so move 5 right to make space

Step 2: Insert 3 at index 0

[3, 5, 8, 4, 2]

Why: 3 placed before 5 to keep sorted order

Step 3: Take element 8, compare with 5, no shift needed

[3, 5, 8, 4, 2]

Why: 8 is greater than 5, stays in place

Step 4: Take element 4, compare with 8, shift 8 right

[3, 5, 8, 8, 2]

Why: 4 is smaller than 8, shift 8 to right

Step 5: Compare 4 with 5, shift 5 right

[3, 5, 5, 8, 2]

Why: 4 is smaller than 5, shift 5 to right

Step 6: Insert 4 at index 1

[3, 4, 5, 8, 2]

Why: 4 placed before 5 to keep sorted order

Step 7: Take element 2, compare with 8, shift 8 right

[3, 4, 5, 8, 8]

Why: 2 is smaller than 8, shift 8 right

Step 8: Compare 2 with 5, shift 5 right

[3, 4, 5, 5, 8]

Why: 2 is smaller than 5, shift 5 right

Step 9: Compare 2 with 4, shift 4 right

[3, 4, 4, 5, 8]

Why: 2 is smaller than 4, shift 4 right

Step 10: Compare 2 with 3, shift 3 right

[3, 3, 4, 5, 8]

Why: 2 is smaller than 3, shift 3 right

Step 11: Insert 2 at index 0

[2, 3, 4, 5, 8]

Why: 2 placed at start to keep sorted order

Result:

Final sorted array: [2, 3, 4, 5, 8]

Annotated Code

DSA Java

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            // Move elements greater than key to one position ahead
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        insertionSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

for (int i = 1; i < arr.length; i++) {

iterate over each element starting from second to insert it into sorted part

int key = arr[i];

store current element to insert

int j = i - 1;

start comparing with previous sorted elements

while (j >= 0 && arr[j] > key) {

shift elements greater than key to right to make space

arr[j + 1] = arr[j];

move element one position right

j--;

move left to check next element

arr[j + 1] = key;

insert key at correct position

Output

2 3 4 5 8 

Complexity Analysis

Time: O(n^2) because in worst case each element is compared with all previous sorted elements

Space: O(1) because sorting is done in place without extra storage

vs Alternative: Compared to bubble sort, insertion sort is often faster on nearly sorted data because it stops early when elements are in order

Edge Cases

empty array

no operations, array remains empty

DSA Java

for (int i = 1; i < arr.length; i++) {

array with one element

no changes, array is already sorted

DSA Java

for (int i = 1; i < arr.length; i++) {

array with all elements equal

no shifts happen, array remains same

DSA Java

while (j >= 0 && arr[j] > key) {

When to Use This Pattern

When you see a problem asking to sort small or nearly sorted data efficiently with simple code, reach for insertion sort because it inserts elements one by one in order.

Common Mistakes

Mistake: Not shifting elements to the right before inserting the key
Fix: Use a while loop to shift all elements greater than key one position right before placing key

Mistake: Inserting key at wrong index after shifting
Fix: Insert key at index j + 1 after shifting elements

Summary

Insertion sort builds a sorted array by inserting each element into its correct position among previously sorted elements.

Use insertion sort for small or nearly sorted arrays where simple and stable sorting is needed.

The key insight is shifting larger elements right to make space for the current element to be inserted in order.

Practice

1. What is the main idea behind the Insertion Sort algorithm?

easy

A. Select the smallest element and swap it with the first unsorted element

B. Divide the array into halves and sort each half separately

C. Swap adjacent elements if they are in the wrong order repeatedly

D. Build the sorted array one element at a time by inserting elements in the correct position

Solution

1. Step 1: Understand insertion sort process

   Insertion sort builds the sorted array by taking one element at a time and placing it in the correct position among the already sorted elements.

2. Step 2: Compare with other sorting methods

   Other options describe different sorting algorithms: divide and conquer (merge sort), swapping adjacent elements (bubble sort), selecting smallest element (selection sort).

3. Final Answer:

   Build the sorted array one element at a time by inserting elements in the correct position -> Option D

4. Quick Check:

   Insertion sort = Insert elements step-by-step [OK]

Hint: Insertion sort inserts elements one by one in order [OK]

Common Mistakes:

• Confusing insertion sort with bubble sort
• Thinking insertion sort divides array into halves
• Mixing insertion sort with selection sort

2. Which of the following is the correct syntax to start the outer loop for insertion sort in Java for an array arr of length n?

easy

A. for (int i = 0; i < n; i++)

B. for (int i = n - 1; i >= 0; i--)

C. for (int i = 1; i < n; i++)

D. for (int i = 1; i <= n; i++)

Solution

1. Step 1: Identify insertion sort loop start

   Insertion sort starts from the second element (index 1) because the first element is considered sorted.

2. Step 2: Check loop conditions

   The loop runs from i = 1 up to i < n (not i <= n) to avoid index out of bounds.

3. Final Answer:

   for (int i = 1; i < n; i++) -> Option C

4. Quick Check:

   Start from second element: i=1 [OK]

Hint: Start outer loop at 1, not 0, in insertion sort [OK]

Common Mistakes:

• Starting loop at 0 instead of 1
• Using i <= n causing index errors
• Looping backwards incorrectly

3. What will be the output array after applying insertion sort on int[] arr = {4, 3, 2, 1};?

medium

A. [1, 2, 3, 4]

B. [4, 3, 2, 1]

C. [1, 3, 2, 4]

D. [2, 3, 4, 1]

Solution

1. Step 1: Trace insertion sort on array {4, 3, 2, 1}

   Start with second element 3: insert before 4 -> {3, 4, 2, 1}. Next 2: insert before 3 -> {2, 3, 4, 1}. Finally 1: insert before 2 -> {1, 2, 3, 4}.

2. Step 2: Confirm final sorted array

   After all insertions, the array is sorted ascending: [1, 2, 3, 4].

3. Final Answer:

   [1, 2, 3, 4] -> Option A

4. Quick Check:

   Insertion sort sorts ascending -> [1, 2, 3, 4] [OK]

Hint: Insertion sort outputs sorted array ascending [OK]

Common Mistakes:

• Assuming array stays unchanged
• Confusing insertion sort with no sorting
• Partial sorting only

4. Consider this insertion sort code snippet in Java:

for (int i = 1; i < arr.length; i++) {
    int key = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j] = key;
}

What is the error in this code?

medium

A. The assignment should be arr[j + 1] = key; instead of arr[j] = key;

B. The loop should start from i = 0 instead of 1

C. The condition in while loop should be arr[j] < key

D. The decrement j-- should be j++

Solution

1. Step 1: Analyze where key is placed after shifting

   After shifting elements greater than key to the right, key should be placed at arr[j + 1] because j was decremented one extra time.

2. Step 2: Identify incorrect assignment

   The code assigns arr[j] = key; which overwrites the wrong index. Correct is arr[j + 1] = key;.

3. Final Answer:

   The assignment should be arr[j + 1] = key; instead of arr[j] = key; -> Option A

4. Quick Check:

   Place key at arr[j+1] after shifting [OK]

Hint: Place key at arr[j+1] after shifting elements [OK]

Common Mistakes:

• Assigning key to arr[j] instead of arr[j+1]
• Starting loop at wrong index
• Wrong while condition direction

5. You have an array int[] arr = {5, 3, 8, 6, 2};. After performing insertion sort, what will be the state of the array after the third iteration of the outer loop?

hard

A. [3, 5, 8, 2, 6]

B. [3, 5, 6, 8, 2]

C. [3, 5, 8, 6, 2]

D. [2, 3, 5, 6, 8]

Solution

1. Step 1: Trace each iteration of insertion sort

   Initial array: {5, 3, 8, 6, 2}
   Iteration 1 (i=1): Insert 3 before 5 -> {3, 5, 8, 6, 2}
   Iteration 2 (i=2): Insert 8 (already in correct place) -> {3, 5, 8, 6, 2}
   Iteration 3 (i=3): Insert 6 before 8 -> {3, 5, 6, 8, 2}

2. Step 2: Confirm array state after third iteration

   After third iteration, array is [3, 5, 6, 8, 2].

3. Final Answer:

   [3, 5, 6, 8, 2] -> Option B

4. Quick Check:

   After 3rd iteration, partial sort up to index 3 [OK]

Hint: Trace each insertion step carefully [OK]

Common Mistakes:

• Assuming full sort after 3 iterations
• Not moving elements correctly
• Mixing up iteration counts