Java Program to Implement Insertion Sort
By Coder Scratchpad on in Java
Insertion Sort is a fundamental sorting algorithm that every beginner programmer should understand. It works by building a sorted portion of the array one element at a time. Each element is compared with the elements in the sorted portion and inserted into its correct position. Although it is not the fastest algorithm for large datasets, it is simple, intuitive, and easy to implement, making it ideal for learning the core concepts of sorting and data organization.
Understanding Insertion Sort is valuable because sorting is an essential part of programming. From arranging scores, organizing dates, or even sorting objects in real-life applications, having a grasp of how sorting works improves problem-solving skills. Practicing Insertion Sort in Java also introduces beginners to loops, array manipulation, and algorithmic thinking, all of which are critical for a strong programming foundation.
Table of Contents
Toggle- Program 1: Basic Insertion Sort Using Loops
- Program 2: Insertion Sort in Descending Order
- Program 3: Recursive Insertion Sort
- Program 4: Insertion Sort Using a Comparator Function
- Program 5: Insertion Sort for Objects
- Frequently Asked Questions (FAQ)
- Conclusion
Program 1: Basic Insertion Sort Using Loops
This program demonstrates the standard iterative approach to Insertion Sort in Java. Each element is picked and inserted into its correct position within the already sorted portion of the array.
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;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] numbers = {12, 11, 13, 5, 6};
insertionSort(numbers);
System.out.print("Sorted array: ");
for (int num : numbers) {
System.out.print(num + " ");
}
}
}
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;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] numbers = {12, 11, 13, 5, 6};
insertionSort(numbers);
System.out.print("Sorted array: ");
for (int num : numbers) {
System.out.print(num + " ");
}
}
}
Here, the outer loop picks each element one by one, while the inner loop shifts larger elements to make room for the selected element. Beginners can visualize how the array gradually becomes sorted, step by step.
Program 2: Insertion Sort in Descending Order
By changing the comparison logic, Insertion Sort can sort numbers from largest to smallest, which is useful in scenarios like ranking or prioritization.
public class InsertionSortDescending {
public static void insertionSortDescending(int[] arr) {
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 + 1] = key;
}
}
public static void main(String[] args) {
int[] numbers = {4, 2, 9, 1, 5};
insertionSortDescending(numbers);
System.out.print("Descending order: ");
for (int num : numbers) {
System.out.print(num + " ");
}
}
}
public class InsertionSortDescending {
public static void insertionSortDescending(int[] arr) {
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 + 1] = key;
}
}
public static void main(String[] args) {
int[] numbers = {4, 2, 9, 1, 5};
insertionSortDescending(numbers);
System.out.print("Descending order: ");
for (int num : numbers) {
System.out.print(num + " ");
}
}
}
A simple change in the comparison operator allows the same logic to reverse the sorting order. Beginners can see how flexible the algorithm is with minor adjustments.
Program 3: Recursive Insertion Sort
Insertion Sort can also be implemented recursively. Each recursive call sorts the first n-1 elements and then inserts the last element in its correct position.
public class RecursiveInsertionSort {
public static void recursiveInsertionSort(int[] arr, int n) {
if (n <= 1) return;
recursiveInsertionSort(arr, n - 1);
int last = arr[n - 1];
int j = n - 2;
while (j >= 0 && arr[j] > last) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = last;
}
public static void main(String[] args) {
int[] numbers = {20, 12, 11, 15, 10};
recursiveInsertionSort(numbers, numbers.length);
System.out.print("Sorted array (recursive): ");
for (int num : numbers) {
System.out.print(num + " ");
}
}
}
public class RecursiveInsertionSort {
public static void recursiveInsertionSort(int[] arr, int n) {
if (n <= 1) return;
recursiveInsertionSort(arr, n - 1);
int last = arr[n - 1];
int j = n - 2;
while (j >= 0 && arr[j] > last) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = last;
}
public static void main(String[] args) {
int[] numbers = {20, 12, 11, 15, 10};
recursiveInsertionSort(numbers, numbers.length);
System.out.print("Sorted array (recursive): ");
for (int num : numbers) {
System.out.print(num + " ");
}
}
}
This version highlights how recursion breaks a problem into smaller subproblems. It helps beginners understand both recursion and the insertion logic simultaneously.
Program 4: Insertion Sort Using a Comparator Function
Java allows the use of a comparator to define custom sorting rules, making Insertion Sort flexible for different data types or sorting criteria.
import java.util.Arrays;
import java.util.Comparator;
public class InsertionSortComparator {
public static void insertionSort(Integer[] arr, Comparator<Integer> comp) {
for (int i = 1; i < arr.length; i++) {
Integer key = arr[i];
int j = i - 1;
while (j >= 0 && comp.compare(key, arr[j]) < 0) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
Integer[] numbers = {7, 3, 5, 1, 9};
insertionSort(numbers, Integer::compareTo);
System.out.println("Sorted using comparator: " + Arrays.toString(numbers));
}
}
import java.util.Arrays;
import java.util.Comparator;
public class InsertionSortComparator {
public static void insertionSort(Integer[] arr, Comparator comp) {
for (int i = 1; i < arr.length; i++) {
Integer key = arr[i];
int j = i - 1;
while (j >= 0 && comp.compare(key, arr[j]) < 0) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
Integer[] numbers = {7, 3, 5, 1, 9};
insertionSort(numbers, Integer::compareTo);
System.out.println("Sorted using comparator: " + Arrays.toString(numbers));
}
}
Using a comparator teaches beginners how to customize sorting for different requirements, such as sorting objects by attributes or applying descending order logic.
Program 5: Insertion Sort for Objects
Insertion Sort can handle complex objects. This example sorts a list of Person objects by age.
import java.util.Arrays;
public class InsertionSortObjects {
public static void insertionSort(Person[] arr) {
for (int i = 1; i < arr.length; i++) {
Person key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j].age > key.age) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
Person[] people = {
new Person("Mary", 25),
new Person("Samantha", 20),
new Person("Edward", 30)
};
insertionSort(people);
System.out.println("Sorted by age: " + Arrays.toString(people));
}
}
class Person {
String name;
int age;
Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return name + " (" + age + ")";
}
}
import java.util.Arrays;
public class InsertionSortObjects {
public static void insertionSort(Person[] arr) {
for (int i = 1; i < arr.length; i++) {
Person key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j].age > key.age) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
Person[] people = {
new Person("Mary", 25),
new Person("Samantha", 20),
new Person("Edward", 30)
};
insertionSort(people);
System.out.println("Sorted by age: " + Arrays.toString(people));
}
}
class Person {
String name;
int age;
Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return name + " (" + age + ")";
}
}
This approach helps beginners understand how algorithms can be applied to real-world data, combining object-oriented programming with algorithmic logic.
Frequently Asked Questions (FAQ)
Here are some questions beginners often have about Insertion Sort in Java:
Q1: Is Insertion Sort efficient for large datasets?
Insertion Sort has a time complexity of O(n²), making it suitable for small arrays or nearly sorted data. For large datasets, consider more efficient algorithms like Quick Sort or Merge Sort.
Q2: Can Insertion Sort handle objects?
Yes, by comparing object attributes, Insertion Sort can sort objects, which is useful for sorting real-world data.
Q3: Why use recursion in Insertion Sort?
Recursion helps in understanding problem decomposition and strengthens algorithmic thinking. Though iterative solutions are more practical, recursion is excellent for learning.
Q4: Can I sort in descending order?
Absolutely. Adjust the comparison in the while loop to reverse the sorting order.
Q5: What is the advantage of using a comparator?
A comparator provides flexibility, allowing sorting based on custom criteria without changing the algorithm’s core logic.
Conclusion
Insertion Sort is a great starting point for beginners in Java. By exploring different implementations—iterative, recursive, comparator-based, and object-based—learners can understand the algorithm deeply and apply it in various scenarios. Practicing these programs helps build confidence in working with arrays, loops, comparisons, and object-oriented programming. The best way to master Insertion Sort is by experimenting with different datasets, observing how each element finds its proper place, and gradually strengthening problem-solving skills.