### 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^{2}) 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 `id`

s 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 ^{2})* 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^{2}) 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).