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 third elements. We repeat this process until our array gets sorted. So, the steps to be followed are:

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

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

Higher-Order Functions in kotlin

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

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

- Start by comparing the current element with the previous element, if the current element is smaller then we switch/swap it with the previous element.
**Why should we start with the second element ?**

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

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

- Before we make the swap, we have to store the current element in a temp variable called "item"

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

- When we handle the second element then we do not have the problem. But when we are dealing with other elements we have to make sure that we are putting the small element in the first position.

The while loop helps the user to see is there any other element is smaller than the 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
}
```

Safe Call Operator [?.] in kotlin

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)
}
```

I am Pavankumar, Having 8.5 years of experience currently working in Video/Live Analytics project.