Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages: 1. Simple implementation: Jon Bentley shows a three-line c version, and a five-line optimized version Efficient for (quite) small data sets, much like other quadratic sorting algorithmsAdaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each component in the input is no more than K places away from its sorted position 2. Stable; i.e., makes not change the relative order of components with equal keys

To perform an insertion sort, begin at the left-most component of the array and invoke insert to insert each component encountered into its correct position. It operates by beginning at the end of the sequence and shifting each component one place to the right until a suitable position is found for the new component.

```
/*
* Copyright (c) 2017 Kotlin Algorithm Club
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in all
* copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
*/
package com.algorithmexamples.sorts
/**
* Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
* Each iteration, insertion sort removes one element from the input data, finds the location it belongs within
* the sorted list, and inserts it there. It repeats until no input elements remain.
*/
@ComparisonSort
@StableSort
class InsertionSort: AbstractSortStrategy() {
override fun <T : Comparable<T>> perform(arr: Array<T>) {
for (i in 1 until arr.size) {
for (j in i downTo 1) {
if (arr[j - 1] < arr[j]) break
arr.exch(j, j - 1)
}
}
}
}
```