Insertion Sort is a fundamental algorithm in computer science. It is known for its simplicity and ease of implementation, making it an excellent starting point for beginners learning about sorting algorithms.

In this blog post, we’ll cover:

- How Insertion Sort works, including its pseudocode
- A step-by-step Java implementation
- Performance analysis of the algorithm
- Pros and cons and when to use the algorithm

Insertion Sort’s straightforward approach makes it valuable for:

- Learning basic sorting concepts
- Handling small datasets efficiently
- Understanding more complex sorting algorithms

Let’s dive in and explore this essential sorting technique!

**What is Insertion Sort?**

**Insertion Sort** works similarly to how you sort a hand of playing cards. You pick one card at a time and place it in the correct position relative to the cards already sorted. The array is conceptually split into two parts: the sorted and unsorted sections. The algorithm picks one element from the unsorted part and inserts it into its correct position in the sorted part.

Below is our visualization tool for seeing **Insertion Sort** in real time!

**Why start at index 1?**

Insertion Sort works by assuming the first element is already sorted (since a single element is trivially sorted). Therefore, the algorithm starts at index 1 and compares the element at that index with the previous ones, inserting it into its correct position in the sorted portion of the array.

**Pseudocode for Insertion Sort**

Here’s the step-by-step pseudocode for Insertion Sort:

procedure insertionSort(arr) for i = 1 to length(arr) - 1 do key = arr[i] j = i - 1 while j >= 0 and arr[j] > key do arr[j + 1] = arr[j] j = j - 1 arr[j + 1] = key

**Step-by-Step Explanation**:

- You iterate through the array starting from the second element (index 1).
- Each element is compared with the elements before it and is inserted into its correct position in the sorted portion of the array.
- The process continues until all elements are sorted.

**Time Complexity of Insertion Sort**

**Best Case**: O(n) – This occurs when the input array is already sorted. In this case, Insertion Sort only needs to make a single pass through the array.**Average Case**: O(n²) – On average, the algorithm needs to compare and shift elements, leading to quadratic time complexity.**Worst Case**: O(n²) – The worst-case scenario occurs when the array is sorted in reverse order, requiring maximum comparisons and shifts.

**Space Complexity of Insertion Sort**

**Space Complexity**: O(1) – Insertion Sort is an in-place sorting algorithm, meaning it sorts the array without requiring any additional memory allocation.

## Java Implementation of Insertion Sort

public class InsertionSort { // Method to perform insertion sort public static void insertionSort(int[] arr) { int n = arr.length; // Start sorting from the second element (index 1) for (int i = 1; i < n; i++) { int key = arr[i]; // Current element to be sorted int j = i - 1; // Move elements of arr[0..i-1] that are greater than key to one position ahead while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } // Place the key in the correct position arr[j + 1] = key; } } // Main method to test the sorting algorithm public static void main(String[] args) { int[] arr = {12, 11, 13, 5, 6}; // Print the original array System.out.println("Original Array: "); printArray(arr); // Perform insertion sort insertionSort(arr); // Print the sorted array System.out.println("Sorted Array: "); printArray(arr); } // Helper method to print the array public static void printArray(int[] arr) { for (int i : arr) { System.out.print(STR."\{i} "); } System.out.println(); } }

**Explanation**:

- The outer loop picks one element (
`key`

) starting from the second element of the array. - The inner
`while`

loop shifts elements that are greater than`key`

one position to the right. - Once the correct position is found, the
`key`

is inserted into its place, ensuring that the left part of the array is always sorted.

We will explain how **Insertion Sort** processes this array element by element and places each element into its correct position in the sorted portion of the array.

**Step-by-Step Walkthrough**

**Step 1: First Element (12)**

- The first element is already sorted, so nothing needs to be done.
**Array after step 1**:`[12, 11, 13, 5, 6]`

**Step 2: Second Element (11)**

- We compare
`11`

with`12`

. Since`11 < 12`

, we shift`12`

one position to the right and insert`11`

at the beginning. **Array after step 2**:`[11, 12, 13, 5, 6]`

**Step 3: Third Element (13)**

- We compare
`13`

with`12`

. Since`13 > 12`

, it is already in the correct position. **Array after step 3**:`[11, 12, 13, 5, 6]`

**Step 4: Fourth Element (5)**

- We compare
`5`

with`13`

,`12`

, and`11`

. Since`5 < 11`

, we shift`13`

,`12`

, and`11`

one position to the right and insert`5`

at the beginning. **Array after step 4**:`[5, 11, 12, 13, 6]`

**Step 5: Fifth Element (6)**

- We compare
`6`

with`13`

,`12`

, and`11`

. Since`6 < 11`

, we shift`13`

,`12`

, and`11`

one position to the right and insert`6`

in its correct position between`5`

and`11`

. **Array after step 5**:`[5, 6, 11, 12, 13]`

**Final Sorted Array**

After all the steps are complete, the final sorted array is:

[5, 6, 11, 12, 13]

**Summary of Steps**:

- The first element is considered sorted.
- The second element (
`11`

) is compared with the first (`12`

) and inserted before it. - The third element (
`13`

) is larger than the sorted portion and remains in place. - The fourth element (
`5`

) is smaller than all previous elements and is inserted at the beginning. - The fifth element (
`6`

) is inserted between`5`

and`11`

, completing the sorting process.

This process is repeated until the entire array is sorted. Insertion Sort works well for small datasets or nearly sorted arrays, as seen here.

## Performance Test: Insertion Sort vs Bubble Sort vs Quick Sort

In this section, we’ll evaluate the performance of three well-known sorting algorithms: **Insertion Sort**, **Bubble Sort**, and **Quick Sort**. By testing these algorithms on different arrays — **random**, **sorted**, **reverse-sorted**, and **partially sorted** — we can better understand their efficiency and behaviour under different conditions.

**Why These Algorithms?**

**Insertion Sort**is a simple algorithm that works efficiently on small or nearly sorted datasets. However, it struggles with large, unsorted data due to its**O(n²)**time complexity in the average and worst cases.**Bubble Sort**is one of the most straightforward sorting algorithms, but it is generally inefficient for large datasets due to its repeated pairwise comparisons, which result in**O(n²)**time complexity in the worst case.**Quick Sort**is widely used because of its average-case**O(n log n)**performance. It performs well on most datasets but can slow down with specific patterns, such as already sorted or reverse-sorted data, depending on how the pivot is chosen.

**Types of Arrays Tested:**

**Random Arrays**: These arrays contain elements in a random order, representing typical real-world datasets.**Sorted Arrays**: These arrays are already in ascending order, representing the best-case scenario for Insertion Sort.**Reverse-Sorted Arrays**: These arrays are in descending order, representing the worst-case scenario for Insertion Sort and Bubble Sort.**Partially Sorted Arrays**: These arrays are half-sorted and half-random, representing real-world cases where data may not be completely unsorted but still requires sorting.

By running this performance test, we aim to identify the strengths and weaknesses of each algorithm and determine which one performs best under various conditions and for different array sizes.

Let’s dive into the performance results and see how each algorithm stacks up!

import java.util.Arrays; import java.util.Random; public class SortingPerformanceTest { // Insertion Sort implementation public static void insertionSort(int[] arr) { int n = arr.length; 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]; j--; } arr[j + 1] = key; } } // Bubble Sort implementation public static void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } // Quick Sort implementation public static void quickSort(int[] arr, int low, int high) { if (low < high) { int pivot = partition(arr, low, high); quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } // Partition function for Quick Sort public static int partition(int[] arr, int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; swap(arr, i, j); } } swap(arr, i + 1, high); return i + 1; } // Helper function to swap elements public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // Generate a partially sorted array public static int[] generatePartiallySortedArray(int size) { Random random = new Random(); int[] arr = random.ints(size, 0, size).toArray(); Arrays.sort(arr, 0, size / 2); // Sort the first half, leave the second half unsorted return arr; } // Helper method to run a performance test public static void benchmark(String name, Runnable sort) { long start = System.nanoTime(); sort.run(); long duration = System.nanoTime() - start; System.out.printf("%s: %.3f ms%n", name, duration / 1e6); // Convert nanoseconds to milliseconds } public static void main(String[] args) { int[] sizes = {1000, 5000, 10000}; // Test with array sizes 1000, 5000, and 10000 Random rand = new Random(); for (int size : sizes) { System.out.println("Array size: " + size); // Generate a random array int[] randomArray = rand.ints(size, 0, size).toArray(); // Performance test for random arrays benchmark("Insertion Sort (random)", () -> { int[] arr = Arrays.copyOf(randomArray, randomArray.length); insertionSort(arr); }); benchmark("Bubble Sort (random)", () -> { int[] arr = Arrays.copyOf(randomArray, randomArray.length); bubbleSort(arr); }); benchmark("Quick Sort (random)", () -> { int[] arr = Arrays.copyOf(randomArray, randomArray.length); quickSort(arr, 0, arr.length - 1); }); // Generate a sorted array int[] sortedArray = Arrays.copyOf(randomArray, randomArray.length); Arrays.sort(sortedArray); // Performance test for sorted arrays benchmark("Insertion Sort (sorted)", () -> insertionSort(Arrays.copyOf(sortedArray, sortedArray.length))); benchmark("Bubble Sort (sorted)", () -> bubbleSort(Arrays.copyOf(sortedArray, sortedArray.length))); benchmark("Quick Sort (sorted)", () -> quickSort(Arrays.copyOf(sortedArray, sortedArray.length), 0, sortedArray.length - 1)); // Generate a reverse-sorted array int[] reverseArray = Arrays.copyOf(sortedArray, sortedArray.length); for (int i = 0; i < reverseArray.length / 2; i++) { swap(reverseArray, i, reverseArray.length - i - 1); } // Performance test for reverse-sorted arrays benchmark("Insertion Sort (reverse)", () -> insertionSort(Arrays.copyOf(reverseArray, reverseArray.length))); benchmark("Bubble Sort (reverse)", () -> bubbleSort(Arrays.copyOf(reverseArray, reverseArray.length))); benchmark("Quick Sort (reverse)", () -> quickSort(Arrays.copyOf(reverseArray, reverseArray.length), 0, reverseArray.length - 1)); // Generate a partially sorted array int[] partiallySortedArray = generatePartiallySortedArray(size); // Performance test for partially sorted arrays benchmark("Insertion Sort (partially sorted)", () -> insertionSort(Arrays.copyOf(partiallySortedArray, partiallySortedArray.length))); benchmark("Bubble Sort (partially sorted)", () -> bubbleSort(Arrays.copyOf(partiallySortedArray, partiallySortedArray.length))); benchmark("Quick Sort (partially sorted)", () -> quickSort(Arrays.copyOf(partiallySortedArray, partiallySortedArray.length), 0, partiallySortedArray.length - 1)); System.out.println(); } } }

### Results

Array Size & Configuration | Insertion Sort (ms) | Bubble Sort (ms) | Quick Sort (ms) |
---|---|---|---|

1000 (Random) | 2.682 | 4.449 | 0.410 |

1000 (Sorted) | 0.013 | 1.822 | 1.984 |

1000 (Reverse) | 6.422 | 0.962 | 2.618 |

1000 (Partially Sorted) | 0.447 | 0.792 | 0.194 |

5000 (Random) | 9.148 | 22.923 | 0.370 |

5000 (Sorted) | 0.033 | 5.197 | 11.387 |

5000 (Reverse) | 4.339 | 16.898 | 10.253 |

5000 (Partially Sorted) | 1.682 | 19.801 | 0.376 |

10000 (Random) | 9.273 | 119.407 | 0.702 |

10000 (Sorted) | 0.066 | 24.298 | 46.132 |

10000 (Reverse) | 19.205 | 66.920 | 32.402 |

10000 (Partially Sorted) | 6.679 | 101.361 | 0.628 |

Note: Times are rounded to three decimal places for readability. Actual performance may vary due to system conditions.

### Key Takeaways:

**Quick Sort is consistently the fastest algorithm**:**Quick Sort**outperformed both**Insertion Sort**and**Bubble Sort**across all tests, particularly with random and partially sorted arrays. For example, with**10000 random elements**, Quick Sort took just**0.702 ms**compared to**119.407 ms**for Bubble Sort and**9.273 ms**for Insertion Sort.

**Insertion Sort excels on sorted arrays**:**Insertion Sort**performed exceptionally well on**sorted arrays**, taking just**0.013 ms**for**1000 sorted elements**and**0.033 ms**for**5000 sorted elements**. This is because**Insertion Sort**has a best-case time complexity of**O(n)**when the array is already sorted.

**Bubble Sort performs poorly on large arrays**:**Bubble Sort**struggles significantly with larger arrays, especially on random and partially sorted arrays. For example, on**10000 random elements**, Bubble Sort took**119.407 ms**, while Quick Sort took only**0.702 ms**.- Even for
**sorted arrays**, Bubble Sort remains inefficient compared to Quick Sort and Insertion Sort.

**Insertion Sort and Bubble Sort are both inefficient on reverse-sorted arrays**:- In the worst case,
**Insertion Sort**and**Bubble Sort**performed poorly on reverse-sorted arrays due to their O(n²) time complexity. For 10000 reverse-sorted elements, Insertion Sort took 19.205 ms, and Bubble Sort took**66.920 ms**, compared to**32.402 ms**for Quick Sort.

- In the worst case,
**Quick Sort remains fast even for larger, partially sorted arrays**:- Quick Sort’s performance on
**partially sorted arrays**was excellent, handling**10000 partially sorted elements**in just**0.628 ms**, significantly outperforming both Insertion Sort (**6.679 ms**) and Bubble Sort (**101.361 ms**).

- Quick Sort’s performance on

### Conclusion:

**Quick Sort**is the best sorting algorithm for general use, particularly for larger datasets.**Insertion Sort**is highly efficient when dealing with already or nearly sorted data.**Bubble Sort**, while simple, is highly inefficient for large datasets and should be avoided unless dealing with very small arrays.

### Why Reverse-Sorted Arrays Are the Worst Case for Insertion Sort and Bubble Sort

Both **Insertion Sort** and **Bubble Sort** have worst-case time complexities of **O(n²)**, which is most apparent when they process **reverse-sorted arrays**. Here’s why reverse-sorted data creates the worst performance for these algorithms:

#### Insertion Sort:

For **Insertion Sort**, the algorithm assumes that elements before the current one are already sorted, and it shifts elements to insert the current element in its correct position. In the case of a **reverse-sorted array**, every element is smaller than the ones that come before it. Therefore, every element has to be compared and shifted to the front of the sorted section.

- For the first element, there are no shifts.
- For the second element, it is compared and shifted once.
- For the third element, it is compared and shifted twice.
- This process continues, resulting in approximately n(n−1)/2n(n-1)/2n(n−1)/2 comparisons and shifts in total, leading to
**O(n²)**time complexity.

**Example**: For a reverse-sorted array like `[5, 4, 3, 2, 1]`

, Insertion Sort will shift `5`

four times to the end, then `4`

three times, and so on.

#### Bubble Sort:

In **Bubble Sort**, the algorithm repeatedly compares adjacent elements and swaps them if they are in the wrong order. With a **reverse-sorted array**, every comparison results in a swap, pushing the largest element to the end of the array. This process has to be repeated for each element.

- In the first pass, the largest element is moved to the last position.
- In the second pass, the second largest element is moved to the second last position.
- This continues until the entire array is sorted.

Because **Bubble Sort** requires **n-1** comparisons and swaps for each pass and the process is repeated **n** times, it leads to **O(n²)** time complexity for reverse-sorted arrays.

**Example**: For the reverse-sorted array `[5, 4, 3, 2, 1]`

, Bubble Sort will compare and swap `5`

with `4`

, then `5`

with `3`

, and so on, moving the largest number to the correct position at each pass.

### Summary:

**Reverse-sorted arrays**are the worst case for both**Insertion Sort**and**Bubble Sort**because both algorithms must move every element to its correct position through many comparisons, shifts (for Insertion Sort), or swaps (for Bubble Sort).- This behaviour leads to
**O(n²)**performance, making both algorithms highly inefficient for reverse-sorted data, particularly as the array grows.

**Pros and Cons of Using Insertion Sort**

**Pros**:

**Simplicity**: Insertion Sort is easy to understand and implement.**Efficient for Small Arrays**: It performs well on small datasets or nearly sorted arrays.**Stable Sorting**: It preserves the relative order of equal elements, making it a stable sorting algorithm.**In-Place Sorting**: Insertion Sort uses constant additional memory (O(1)).

**Cons**:

**Inefficient for Large Arrays**: Its O(n²) time complexity makes it inefficient for large datasets compared to algorithms like QuickSort or MergeSort.**More Comparisons and Shifts**: Insertion Sort performs a high number of comparisons and shifts in the worst case.

**When to Use Insertion Sort**

Insertion Sort is typically used in the following scenarios:

**Small Arrays**: When working with small arrays (e.g., fewer than 20 elements), the simplicity of Insertion Sort makes it a reasonable choice.**Nearly Sorted Arrays**: Insertion Sort performs exceptionally well on nearly sorted arrays, where it can achieve close to O(n) time complexity.**Part of a Hybrid Sorting Algorithm**: Insertion Sort is often used as a subroutine in more efficient sorting algorithms like**TimSort**and**IntroSort**, where it is employed to handle small partitions.

## Conclusion

**Insertion Sort** is a simple and intuitive algorithm, making it an excellent choice for small or nearly sorted datasets. While it’s not suitable for large datasets due to its O(n²) time complexity, it is still an important algorithm to learn. Its role in hybrid algorithms like **TimSort** highlights its practical utility for optimizing the performance of complex sorting operations.

Congratulations on reading to the end of this tutorial!

Read the following articles to learn how to implement Insertion Sort:

In Python – How to do Insertion Sort in Python

In C++ – How to Do Insertion Sort in C++

In Rust – How to do Insertion Sort in Rust

Have fun and happy researching!

Suf is a senior advisor in data science with deep expertise in Natural Language Processing, Complex Networks, and Anomaly Detection. Formerly a postdoctoral research fellow, he applied advanced physics techniques to tackle real-world, data-heavy industry challenges. Before that, he was a particle physicist at the ATLAS Experiment of the Large Hadron Collider. Now, he’s focused on bringing more fun and curiosity to the world of science and research online.