Implementation of Insertion Sort Algorithm in Java

Insertion sort is an algorithm used to sort a list of items in ascending, descending or any other custom order. In this article, we’ll implement a basic version of insertion sort algorithm in Java which can sort a given list of numbers in ascending order. We’ll then explore several practical variations, including sorting in descending order and handling custom objects with flexible sorting criteria.

Prerequisites:

Basic Insertion Sort Implementation

Let’s start with the standard iterative implementation of insertion sort. This version sorts an array in ascending order by repeatedly taking an element and inserting it into its correct position in the already sorted portion of the array.

public class InsertionSort {
  public static void insertionSort(int[] arr) {
    // Handle empty or single-element arrays
    if (arr == null || arr.length <= 1) {
      return;
    }
    
    // Iterate through array starting from second element
    for (int i = 1; i < arr.length; i++) {
      int key = arr[i];
      int j = i - 1;
      
      // Move elements greater than key ahead
      while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
      }
      
      // Place key in its correct position
      arr[j + 1] = key;
    }
  }

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

  public static void main(String[] args) {
    // Test with a simple array
    int[] arr = {64, 34, 25, 12, 22, 11, 90};
    System.out.print("Original array: ");
    printArray(arr);
    
    insertionSort(arr);
    
    System.out.print("Sorted array: ");
    printArray(arr);
    
    // Test with duplicates
    int[] arrWithDuplicates = {4, 3, 2, 4, 1, 2};
    System.out.print("Original array with duplicates: ");
    printArray(arrWithDuplicates);
    
    insertionSort(arrWithDuplicates);
    
    System.out.print("Sorted array with duplicates: ");
    printArray(arrWithDuplicates);
  }
}

Output:

Original array: 64 34 25 12 22 11 90 
Sorted array: 11 12 22 25 34 64 90 
Original array with duplicates: 4 3 2 4 1 2 
Sorted array with duplicates: 1 2 2 3 4 4

Sorting in Descending Order

Sometimes we need to sort arrays in reverse order. Here’s a modified version of insertion sort that arranges elements from largest to smallest. The main difference is in the comparison operator - we use < instead of > to achieve descending order.

public class InsertionSortDesc {
  public static void insertionSortDesc(int[] arr) {
    if (arr == null || arr.length <= 1) {
      return;
    }
    
    for (int i = 1; i < arr.length; i++) {
      int key = arr[i];
      int j = i - 1;
      
      // Notice the < operator instead of >
      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};
    System.out.print("Original array: ");
    printArray(arr);
    
    insertionSortDesc(arr);
    
    System.out.print("Sorted array (descending): ");
    printArray(arr);
  }
}

Output:

Original array: 64 34 25 12 22 11 90 
Sorted array (descending): 90 64 34 25 22 12 11

Sorting Custom Objects

In real-world applications, we often need to sort objects based on specific attributes. Here’s a generic implementation that can sort any type of object using a custom comparator. This makes it very flexible and useful for sorting complex data structures.

import java.util.Comparator;

public class InsertionSortGeneric<T> {
  public void sort(T[] arr, Comparator<? super T> comparator) {
    if (arr == null || arr.length <= 1) {
      return;
    }
    
    for (int i = 1; i < arr.length; i++) {
      T key = arr[i];
      int j = i - 1;
      
      while (j >= 0 && comparator.compare(arr[j], key) > 0) {
        arr[j + 1] = arr[j];
        j--;
      }
      
      arr[j + 1] = key;
    }
  }

  // Example usage with a Student class
  static class Student {
    private String name;
    private int age;
    
    public Student(String name, int age) {
      this.name = name;
      this.age = age;
    }
    
    public String getName() { return name; }
    public int getAge() { return age; }
    
    @Override
    public String toString() {
      return name + " (" + age + ")";
    }
  }

  public static void main(String[] args) {
    // Create an array of students
    Student[] students = {
      new Student("Alice", 20),
      new Student("Bob", 19),
      new Student("Charlie", 21)
    };
    
    InsertionSortGeneric<Student> sorter = new InsertionSortGeneric<>();
    
    // Sort by age
    System.out.println("Sorting by age:");
    sorter.sort(students, Comparator.comparingInt(Student::getAge));
    printArray(students);
    
    // Sort by name
    System.out.println("\nSorting by name:");
    sorter.sort(students, Comparator.comparing(Student::getName));
    printArray(students);
    
    // Sort by age in descending order
    System.out.println("\nSorting by age (descending):");
    sorter.sort(students, (s1, s2) -> s2.getAge() - s1.getAge());
    printArray(students);
  }

  private static <T> void printArray(T[] arr) {
    for (T item : arr) {
      System.out.println(item);
    }
  }
}

Output:

Sorting by age:
Bob (19)
Alice (20)
Charlie (21)

Sorting by name:
Alice (20)
Bob (19)
Charlie (21)

Sorting by age (descending):
Charlie (21)
Alice (20)
Bob (19)

What’s Next?

Now that you’ve learned how to implement insertion sort in Java and its various applications, you might want to explore: