Insertion sort is similar to arranging the documents of a bunch of students in order of their ascending roll number.

**Starting from the second element, we compare it with the first element and swap it if it is not in order**. Similarly, we take the third element in the next iteration and place it at the right place in the subarray of the first and second elements (as the subarray containing the first and second elements is already sorted).

We repeat this step with the fourth element of the array in the next iteration and place it at the right position in the subarray containing the first, second and the third elements. We repeat this process until our array gets sorted. So, the steps to be followed are:

Every iteration, smallest element will be added to unsorted array. Let’s consider this scenario.

- Consider, You have 10 elements in array.
- 1st iteration(from the second element in array) puts smallest element into the position 1. We will call it as sorted array. Remaining 9 elements will call as unsorted array.
- Now in 2nd iteration, smallest element from unsorted array will be put into 1st position. Now, there will be 2 elements in sorted array and 8 elements into unsorted array.
- Same iteration will continue until we reached to 0 element in unsorted array.

- First and foremost, you can use this method for list and arrays with litle modifications. Considering List in this example
- Check number of elements in the list/array, if the number of element are lesser than 2, then no need to sor as it is already sorted. I would be funny, if we try to sort an array/list with 1 element

```
if (items.isEmpty() || items.size<2){
return items
}
```

We will be starting the loop from the second element because we wanted to compare the element with previous element only. (With changes in logic you can use first element as well.)

```
for (count in 1..items.count() - 1){
```

```
val item = items[count]
var i = count
```

The while loop helps user to see is there any other element is smaller than current element by decrementing the position from "current-1" position. If any small element is present then we swap it.

```
while (i>0 && item < items[i - 1]){
items[i] = items[i - 1]
i = i - 1
}
```

Complete program for Insertion sort in Kotlin

```
fun insertionsort(items:MutableList<Int>):List<Int>{
if (items.isEmpty() || items.size<2){
return items
}
for (count in 1..items.count() - 1){
// println(items)
val item = items[count]
var i = count
while (i>0 && item < items[i - 1]){
items[i] = items[i - 1]
i -= 1
}
items[i] = item
}
return items
}
fun main(args: Array<String>) {
val names = mutableListOf(8, 3, 2, 7, 4)
println(names)
var ordered = insertionsort(names)
println(ordered)
}
```

It is a simple Sorting algorithm which sorts the array by shifting elements one by one. Following are some of the important characteristics of Insertion Sort

- It has one of the simplest implementation
- It is efficient for smaller data sets, but very inefficient for larger lists.
- Insertion Sort is adaptive, that means it reduces its total number of steps if given a partially sorted list, hence it increases its efficiency.
- It is better than Selection Sort and Bubble Sort algorithms
- Its space complexity is less, like Bubble Sorting, inerstion sort also requires a single additional memory space.
- It is Stable, as it does not change the relative order of elements with equal keys

Insertion sort is a good choice when the array to be sorted is almost sorted. This is because there will be less number of swaps.

On the contrary, insertion is slow because all the elements after an element that is not in order have to be moved up, therefore not good for big arrays that are not partially sorted.

In any case, the insertion sort runs in `O(N2)`

time for random data. For data that is already sorted or almost sorted, the insertion sort does much better.

When data is in order, the condition in the inner for loop is never true, so it becomes a simple statement in the outer loop, which executes N-1 times. In this case the algorithm runs in `O(N)`

time. If the data is almost sorted, insertion sort runs in almost `O(N)`

time.

However, for data arranged in inverse sorted order, every possible comparison and shift is carried out, so the insertion sort runs no faster than the bubble sort.