Insertion Sort Comparable Array Items in Java

Insertion sort is one of the most common sorting algorithms.

Insertion sort algorithm achieves expected output by applying following steps :

1-) Start from the beginning index
2-) Compare next element with the previous item
3-) If current element is smaller than the previous element than swap elements
4-) Repeat step 3 until a sorted array is achieved

Space and time complexity values are :

Worst case performance О(n²)
Best case performance О(n)
Average case performance О(n²)

There is an animation for the insertion sort algorithm at :

Following is the Java implementation of the Insertion Sort algorithm where the sort method accepts an array of Comparable  items as input parameter.

package basics;

public class InsertionSort {

 public static void sort(Comparable[] a) {

  // Sort a[] into increasing order.
  int N = a.length;
  
  // Insert a[i] among a[i-1], a[i-2], a[i-3]....
  for (int i = 1; i < N; i++) { 
   for ( int j = i; j > 0 && ( (a[j].compareTo( a[j-1]))< 0 ); j--)
   {
       Comparable temp = a[j];
       a[j] = a[j - 1];
       a[j - 1] = temp;    
   }    
  }

 }

 public static void main(String[] args) {

  String[] strArr = { "S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E" };

  System.out.println("Before Sort = ");
  for (int i = 0; i < strArr.length; i++)
   System.out.print(strArr[i] + " ");
  System.out.println("\n");

  sort(strArr);

  System.out.println("After Sort = ");
  for (int i = 0; i < strArr.length; i++)
   System.out.print(strArr[i] + " ");
  System.out.println();

  Integer[] intArr = { 9, 8, 7, 6, 6, 5, 4, 3, 2, 2, 1 };

  System.out.println();
  System.out.println("Before Sort = ");
  for (int i = 0; i < intArr.length; i++)
   System.out.print(intArr[i] + " ");
  System.out.println("\n");

  sort(intArr);

  System.out.println("After Sort = ");
  for (int i = 0; i < intArr.length; i++)
   System.out.print(intArr[i] + " ");
  System.out.println();
 }
}

Create an InsertionSort.java file in your workspace.

When the main method inside the InsertionSort class executed it is going to print :

Before Sort =
S O R T E X A M P L E

After Sort =
A E E L M O P R S T X

Before Sort =
9 8 7 6 6 5 4 3 2 2 1

After Sort =
1 2 2 3 4 5 6 6 7 8 9


Because sort method accepts an array or Comparable items, so it is safe to send an array of items where each item implements Comparable interface in Java.

Integer and String classes in Java implement Comparable interface so it is acceptable to send this types as parameters to sort method.