Insertion Sort Algorithm in Java

Insertion Sort Algorithm in Java

This article gives provides an overview on Insertion Sort together with an implementation in Java.

Insertion sort is a sorting algorithm that builds the final sorted array (or list) one item at a time. The algorithm iterates over the list and removes the current element, finds the location within the sorted part of the list, and inserts it there. This process is repeated until the whole list is sorted.

Algorithm Classification

The following table contains information about the analysis of the Insertion Sort algorithm. It defines the worst, average and best cases in terms of time complexity and also the worst case in space complexity.

AttributeValue
ClassSorting Algorithm
ClassificationInternal, In-place, Stable Algorithm
Data StructureArray
Time Complexity: BestΩ(n)
Time Complexity: AverageΘ(n2)
Time Complexity: WorstO(n2)
Space Complexity: WorstO(1)

Algorithm Classification: Insertion Sort

Please use the following link for an explanation on Big-O notation and what is good, fair and bad.

Insertion Sort In Java

The InsertionSort class implements the Insertion Sort algorithm for sorting an array of integers.

public final class InsertionSort {
    
    public void sort(int[] collection) {
        if (collection != null) {
            insertionSort(collection);
        } else {
            throw new IllegalArgumentException("Input parameter for array to sort is null.");
        }
    } 
    
  
    private void insertionSort(int[] collection) {
        int arrayLength = collection.length;
        
        for (int unsortIndex = 1; unsortIndex < arrayLength;  unsortIndex++) {
            int newElement = collection[unsortIndex];
            int iterator = 0;

            for (iterator = unsortIndex; iterator > 0 && collection[iterator - 1] > newElement; iterator--) {
                collection[iterator] = collection[iterator - 1];
            }
            collection[iterator] = newElement;
        }
    }
}

Sample Code (GitHub)

The code example can be downloaded from Github from the following link.

Finally

The Insertion Sort algorithm forms part of a larger group of sorting algorithms. Learning through experience is the reason I created this post about the implementation of the Insertion Sort algorithm in Java. I have learned a lot about how others have solved the Insertion Sort algorithm in other languages including different implementations in Java.

Learning how to solve difference problems and algorithms with certain techniques, one starts to develop certain pattern recognition abilities which will help you in future when similar problems arise.