Insertion Sort in Java: A Simple and Efficient Algorithm

Insertion sort is a simple sorting algorithm that builds a sorted array one element at a time by shifting larger elements to the right and inserting the current element into its correct position. Efficient for small or nearly sorted arrays, it has a time complexity of O(n^2) in the worst case and O(1) space complexity.

Introduction

In this blog, we will learn how insertion sort works. Insertion sort is a straightforward sorting algorithm that builds the final sorted array one element at a time. It's efficient for small data sets and is often used as part of more complex sorting algorithms.

Working of Insertion Sort

1. Start with the second element of the array.
2. Compare it with the previous elements.
3. If it's smaller, shift the larger elements right.
4. Insert the element in its correct position.
5. Repeat for all elements.

   import java.util.Arrays;
   public class InsertionSortExample {
       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;
           }
       }
       public static void main(String[] args) {
           int[] arr = {64, 34, 25, 12, 22, 11, 90};
           insertionSort(arr);
           System.out.println(Arrays.toString(arr));
       }
   }
   

Flow Diagram of the above example

Time Complexity

• Best Case: O(n) when the array is already sorted.
• Average and Worst Case: O(n^2).

Space Complexity

O(1) as it sorts in place.

Advantages

• Simple implementation
• Efficient for small data sets
• Adaptive (efficient for partially sorted arrays).

Disadvantages

Inefficient for large data sets.

Summary

Insertion sort shines in scenarios where the data is nearly sorted or when sorting small arrays. Its simplicity makes it a good choice for educational purposes and as a building block for more complex algorithms.