1. Introduction
Insertion sort is an algorithm used for sorting. For example, sorting a list of number or a deck of cards. In this blog post we'll briefly explain how insertion sort works and give a couple of implementations in Kotlin and Java.
2. Background
As you will learn from the explanation in the next chapter, insertion sort is a fairly basic algorithm. Many people that sort a hand of cards, probably do this using insertion sort without realizing it. Because of this, we don't exactly know how old this algorithm is, but we can say that it has been around for a long time. The advantage of insertion sort is that it is a stable sorting algorithm. However, as we will explain in the last chapter, it is not efficient to use on large data sets.
3. How it works
Say we want to sort the following array of numbers (the numbers above the values are the index numbers, A[2] = 6):
Since we are going to sort our array in place, we will introduce the pointer j. We will initially point j to
index 0. The greyed-out part is the sorted subset of A. Because j = 0, we don't have to sort anything.
Let's move on to the next number. We increase j by one: j = 1. Now we have to compare A[j] to its preceding
element A[j - 1]. Since A[j] = 3 is smaller than A[j - 1] = 8, we are going to swap their values.
Now we continue to the next element, we increase j to 2. Since A[j] = 6 is lesser than A[j - 1], we are going to
swap them. After swapping, we have to continue checking whether 6 is greater or smaller than its preceding elements.
Because 6 is greater than 3, we don't have to swap anymore.
And finally, we move over to our last element in A. Since A[j] = 1 is smaller than any other element in A, we can
keep swapping it to the left until it's at the start.
4. Kotlin implementation
The following Kotlin implementation sorts the given array in place using insertion sort (available on GitHub):
1fun main() { 2 val input = intArrayOf(8, 3, 6, 1, 9, 20, 0) 3 val output = insertionSort(input) 4 println(output.contentToString()) 5} 6 7fun insertionSort(input: IntArray): IntArray { 8 for (j in 1 until input.size) { 9 val key = input[j] 10 var i = j - 1 11 12 while (i >= 0 && input[i] > key) { 13 input[i + 1] = input[i] 14 i-- 15 } 16 17 input[i + 1] = key 18 } 19 20 return input 21}
On line 2 we have our unsorted array of integers that we'd like to sort. Lines 7-21 contains our insertion sort implementation. Line 8 starts our outer loop, that loops through all input array entries (note that it skips the first element). Then, on line 12, we compare whether the picked element from the outer loop needs to be swapped to the left.
5. Java implementation
For our Java implementation (GitHub), we don't sort integers,
but Person objects by their age. We made Person implement Comparable, so we can add a compareTo function, that
determines whether a person is older, younger or the same age as another person:
1public class Person implements Comparable<Person> { 2 3 private final String name; 4 private final int age; 5 6 public Person(String name, int age) { 7 this.name = name; 8 this.age = age; 9 } 10 11 @Override 12 public int compareTo(final Person o) { 13 if (age > o.getAge()) { 14 return 1; 15 } else if (age < o.getAge()) { 16 return -1; 17 } 18 19 return 0; 20 } 21 22 public int getAge() { 23 return age; 24 } 25 26 public String toString() { 27 return name + " (" + age + ")"; 28 } 29}
Then, in our App class, we create a list of Person and print the outcome after insertion sorting them:
1public class App { 2 3 public static void main(final String[] args) { 4 final Person person0 = new Person("Penny", 8); 5 final Person person1 = new Person("Ruby", 3); 6 final Person person2 = new Person("Johnny", 6); 7 final Person person3 = new Person("Mark", 1); 8 final Person person4 = new Person("Larry", 9); 9 final Person person5 = new Person("Karen", 20); 10 final Person person6 = new Person("Cecelia", 0); 11 12 final List<Person> people = new ArrayList<>(); 13 people.add(person0); 14 people.add(person1); 15 people.add(person2); 16 people.add(person3); 17 people.add(person4); 18 people.add(person5); 19 people.add(person6); 20 21 final List<Person> sortedPeople = insertionSort(people); 22 System.out.println(sortedPeople); 23 } 24 25 public static List<Person> insertionSort(final List<Person> list) { 26 for (int j = 1; j < list.size(); j++) { 27 final Person k = list.get(j); 28 int i = j - 1; 29 30 while (i >= 0 && list.get(i).compareTo(k) > 0) { 31 list.set(i + 1, list.get(i)); 32 i--; 33 } 34 35 list.set(i + 1, k); 36 } 37 38 return list; 39 } 40}
Between lines 4 and 19 we create our list of Person that we'd like to sort. On line 25 we define our insertionSort
method. Line 26 starts the outer for-loop that loops over all entries of the input list. Then, again, for each of these
entries we have a while-loop (line 30) that swaps items to the left, if needed. You see that is it quite similar as the
Kotlin implementation.
6. Efficiency
The running time of insertion sort is O(n^2). In the best-case scenario, in which the input already is sorted, it
is O(n). If you have taken a look at the code implementations, you would have seen an outer and inner loop, this
causes the complexity to be quadratic. Because of this, it is not recommended to use insertion sort on large data sets.
However, on (relatively) small data sets, it is a good option.
This concludes the short introduction to insertion sort. If you want to learn more about this algorithm, we recommend you dive deeper into the proof and correctness of the algorithm. That way you'll understand the algorithm even more. All code provided in this blog post are available on GitHub.
