In this tutorial, we will write a Program to implement the Insertion Sort algorithm in Kotlin.

Insertion sort is a more useful algorithm. Like bubble sort and selection sort, insertion sort has an average time complexity of O(n²), but the performance of insertion sort can vary. The more the data is already sorted, the less work needs to do. 

Insertion sort has the best time complexity of O(n) if the data is already sorted.

Insertion Sort Algorithm in Kotlin

Let's write the Kotlin program to Sort an Array of elements as well as a List of elements in ascending order:

import java.util.*

fun <E: Comparable<E>> Array<E>.sort() {
    val len = size
    for (i in 1 until len) {
        var key = this[i]
        var j = i - 1;

        while(j >= 0 && this[j] > key) {
            this[j + 1] = this[j]
            j--
        }
        this[j + 1] = key
    }
}

fun <E: Comparable<E>> List<E>.sort(): List<E> {
    val len = size
    val resultList = toMutableList()
    for (i in 1 until len) {
        var key = resultList[i]
        var j = i - 1;

        while(j >= 0 && resultList[j].compareTo(key) > 0) {
            resultList[j + 1] = resultList[j]
            j--
        }
        resultList[j + 1] = key
    }
    return resultList
}

fun main(args: Array<String>) {
    println("Sorting Array of elements")
    val nums = arrayOf(2, 12, 89, 23, 76, 43, 12)
    nums.sort()
    println(Arrays.toString(nums))
    
    println()
    
    println("Sorting List of elements")
    val nums1 = listOf(2, 12, 89, 23, 76, 43, 12)
    val result = nums1.sort()
    println(result)
}

Output:

Sorting Array of elements
[2, 12, 12, 23, 43, 76, 89]

Sorting List of elements
[2, 12, 12, 23, 43, 76, 89]

Sorting Array of elements:

fun <E: Comparable<E>> Array<E>.sort() {
    val len = size
    for (i in 1 until len) {
        var key = this[i]
        var j = i - 1;

        while(j >= 0 && this[j] > key) {
            this[j + 1] = this[j]
            j--
        }
        this[j + 1] = key
    }
}

Sorting List of elements:

fun <E: Comparable<E>> List<E>.sort(): List<E> {
    val len = size
    val resultList = toMutableList()
    for (i in 1 until len) {
        var key = resultList[i]
        var j = i - 1;

        while(j >= 0 && resultList[j].compareTo(key) > 0) {
            resultList[j + 1] = resultList[j]
            j--
        }
        resultList[j + 1] = key
    }
    return resultList
}

Related Data Structures and Algorithms in Kotlin

1. Bubble Sort Algorithm in Kotlin
2. Heap Sort Algorithm in Kotlin
3. Insertion Sort Algorithm in Kotlin
4. Merge Sort Algorithm in Kotlin
5. Quick Sort Algorithm in Kotlin
6. Selection Sort Algorithm in Kotlin
7. Stack Data Structure Implementation in Kotlin
   
8. Queue Data Structure Implementation in Kotlin
   
9. Deque Implementation in Kotlin
   
10. Singly Linked List Implementation in Kotlin
    
11. Doubly Linked List Implementation in Kotlin
    
12. Circular Linked List Implementation in Kotlin