Insertion Sort in Java

Introduction

Sorting is a crucial aspect of digesting data. For us humans, it's much more natural to sort things that have something in common like the date of publishing, alphabetical order, articles belonging to an author, from smallest to largest, etc. This makes it a lot easier to comprehend the data as it's logically connected rather than dispersed all around.

And just as important, sorted arrays are easier for computers to work with. For example, a sorted array can be searched much faster, like with the binary search algorithm, which runs in O(logn) time. An algorithm like this just doesn't work without a sorted array.

Insertion Sort

Insertion Sort is one of the simpler sorting algorithms, which works considerably faster on smaller collections than the introductory Bubble Sort and even Selection Sort even though they're all simple quadratic (O(n²) algorithms.

It's great for nearly sorted and small collections (~10 elements) which makes it extremely useful when used in combination with other, more advanced sorting algorithms such as Quicksort or Merge Sort. Java's official sort() implementation from the Collections API used a Dual Pivot Quicksort, though resorted to Insertion Sort for collections of size 7.

It is generally implemented imperatively (though it can also be recursive), and represents an in-place, stable algorithm that works wonders on small datasets.

This means that it preserves the relative order of duplicate elements after sorting (in-place) and doesn't require any additional memory for sorting with a constant O(1) space complexity (stable).

Insertion Sort works a lot like humans sort cards in their hands by dividing the collection into two parts - sorted and unsorted.

It then traverses the unsorted partition and inserts each element in their relative correct place in the sorted array.

Here's a visual representation of how it works:

If this doesn't make much sense now, it's explained step-by-step in the implementation below alongside the code.

Implementation

That being said, let's go ahead and implement the algorithm on primitive integer arrays and a collection of objects with a custom compareTo() method to define comparison criteria.

We could also implement the Comparable interface and overridde the compareTo() method for defining the comparison criteria, and using the Collections API, simply calling the sort() method provided there. However, that way, we don't implement our own sorting logic.

Sorting Arrays

Sorting primitive integer arrays is quick and straightforward using Insertion Sort:

public static void insertionSort(int array[]) {
    for (int j = 1; j < array.length; j++) {
        int current = array[j];
        int i = j-1;
        while ((i > -1) && (array[i] > current)) {
            array[i+1] = array[i];
            i--;
        }
        array[i+1] = current;
    }
}

The iteration starts on the second element (the first one is by default considered sorted), and compares the first element of the unsorted array with the last element of the sorted array.

The unsorted element is "safe-kept" in the variable current and if the highest element in the sorted array is bigger than the current variable - the adequate portion of the sorted array is shifted to the right.

Please note that they're not swapped, it's shifted to the right and now both array[j] (accessed through array[i+1]) and array[i] hold the same value.

Then, regardless of whether a portion of the sorted array is shifted to the right, we set the array[j] to current, effectively inserting the safe-kept integer into its right place.

If the current element isn't smaller than the biggest sorted element (i.e. it's bigger), it's simply inserted at the end where it belongs.

Let's go ahead and populate a small array of integers and then sort it:

int[] array = new int[]{1, 7, 5, 6, 9, 4, 2, 3};
insertionSort(array);
System.out.println(Arrays.toString(array));

Running this piece of code will yield:

[1, 2, 3, 4, 5, 6, 7, 9]

Sorting ArrayLists

Sorting an ArrayList is a more practical/real-world example that you'll probably encounter a lot more often than primitive integers.

Since we're sorting objects depending on certain criteria, let's first define a class for our Element of a collection:

public class Element {
    private int id;

    public Element(int id) {
        this.id = id;
    }

    // Getters and setters

    public int compareTo(Element element) {
        int res = 0;
        if (this.id < element.getId()) {
            res = -1;
        }
        if (this.id > element.getId()) {
            res = 1;
        }
        return res;
    }
}

It contains a compareTo() method which accepts another Element to be compared to. In this mundane implementation, their ids are being compared, though here is where you can get creative.

Let's rework the algorithm to sort these objects instead:

public static void insertionSortArrayList(List<Element> list) {
    for (int j = 1; j < list.size(); j++) {
        Element current = list.get(j);
        int i = j-1;
        while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
            list.set(i+1, list.get(i));
            i--;
        }
        list.set(i+1, current);
    }
}

Not much has changed, expect for using the methods provided by a List and comparing the elements with our custom compareTo() method. Here, we check if the result of the comparison is 1 since that means that the first element is bigger than the second as defined in our method.

Now, let's populate an ArrayList with some elements and shuffle it:

List<Element> list = new ArrayList<>();

// Create elements w/ IDs 0-24
for (int i = 0; i < 25; i++) {
    list.add(new Element(i));
}

// Move the elements to a random order
Collections.shuffle(list);

And now, let's sort that list:

// Print list before sorting
list.forEach(e -> System.out.print(e.getId() + ", "));

// Sort the list
insertionSortArrayList(list);

System.out.println();

// Print sorted list
list.forEach(e -> System.out.print(e.getId() + ", "));

This piece of code will yield us:

4, 2, 6, 7, 0, 5, 9, 1, 8, 3,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

Time Complexity

The time complexity, both average and worst of Insertion sort is O(n²) which is fairly terrible. There are much better time complexities available through other, more advanced sorting algorithms, though what makes Insertion Sort stand out is how fast it is on nearly sorted and small collections.

Let's try timing it through 5 runs of small collections and 5 runs of large collections.

List<Element> list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
    list.add(new Element(i));
}

Collections.shuffle(list);

// Print shuffled list
list.forEach(e -> System.out.print(e.getId() + ", "));

long startTime1 = System.nanoTime();
insertionSort.insertionSortArrayList(list);
long endTime1 = System.nanoTime();

// Print sorted collection
list.forEach(e -> System.out.print(e.getId() + ", "));
System.out.println();

// Print runtime in nanoseconds
System.out.println("Insertion Sort runtime: " + (endTime1 - startTime1));

Insertion Sort (10)	Time(s)
First Run	0.000058
Second Run	0.000085
Third Run	0.000073
Fourth Run	0.000060
Fifth Run	0.000073

Insertion Sort (10k)	time(s)
First Run	0.091
Second Run	0.125
Third Run	0.104
Fourth Run	0.108
Fifth Run	0.123

Compared to Bubble Sort which has the same time complexity, Insertion Sort is ~5 times faster.

Conclusion

Insertion Sort is one of the simpler sorting algorithms, which works considerably faster on smaller collections than the introductory Bubble Sort and even Selection Sort even though they're all simple quadratic (O(n²) algorithms.

It's great for nearly sorted and small collections (~10 elements) which makes it extremely useful when used in combination with other, more advanced sorting algorithms such as Quicksort or Merge Sort.

It is generally implemented imperatively (though it can also be recursive), and represents an in-place, stable algorithm that works wonders on small datasets.

This means that it preserves the relative order of duplicate elements (in-place) and doesn't require any additional memory for sorting with a constant O(1) space complexity (stable).!