Sorting is a fundamental part of programming. Whether you’re working with numbers, strings, or custom objects, knowing how sorting algorithms work builds your understanding of how data is organized behind the scenes. In this guide, we’ll explore the Kotlin Insertion Sort algorithm in detail, walking through its logic and code.

What Is Insertion Sort?

Insertion sort is one of the simplest sorting algorithms. It works the same way many people sort playing cards:

• Start with the first card in your hand.
• Pick the next card and insert it into the right position among the already sorted cards.
• Repeat this until all cards are sorted.

In other words, insertion sort builds the sorted list one element at a time.

Why Learn Insertion Sort in Kotlin?

While Kotlin offers built-in sorting functions like sorted() or sortBy(), understanding Kotlin Insertion Sort helps you:

• Learn the logic behind sorting.
• Improve problem-solving and algorithmic thinking.
• Understand time complexity (important in interviews).
• Get hands-on with Kotlin basics like loops, arrays, and variables.

How Insertion Sort Works: Step-by-Step

Let’s break it down:

1. Start with the second element of the array (since the first element is already “sorted”).
2. Compare it with the elements before it.
3. If it’s smaller, shift the larger element one position to the right.
4. Insert the element into the correct position.
5. Repeat for all elements until the entire array is sorted.

Kotlin Insertion Sort Code

Here’s a clean implementation of the algorithm in Kotlin:

fun insertionSort(arr: IntArray) {
    val n = arr.size
    for (i in 1 until n) {
        val key = arr[i]
        var j = i - 1

        // Move elements greater than key one step ahead
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]
            j--
        }
        arr[j + 1] = key
    }
}

fun main() {
    val numbers = intArrayOf(9, 5, 1, 4, 3)
    println("Before sorting: ${numbers.joinToString()}")

    insertionSort(numbers)

    println("After sorting: ${numbers.joinToString()}")
}

• fun insertionSort(arr: IntArray) → We define a function that takes an integer array as input.
• for (i in 1 until n) → Loop starts from index 1 (since index 0 is already “sorted”).
• val key = arr[i] → The current element we want to insert in the right position.
• while (j >= 0 && arr[j] > key) → Shift elements greater than key one step forward.
• arr[j + 1] = key → Place the element in its correct spot.

The main function demonstrates sorting an array [9, 5, 1, 4, 3].

• Before sorting: 9, 5, 1, 4, 3
• After sorting: 1, 3, 4, 5, 9

Time Complexity of Insertion Sort

• Best Case (Already Sorted): O(n)
• Worst Case (Reverse Sorted): O(n²)
• Average Case: O(n²)

Insertion sort is not the most efficient for large datasets, but it works well for small arrays and nearly sorted data.

Advantages of Kotlin Insertion Sort

• Easy to implement and understand.
• Works efficiently for small or nearly sorted data.
• Stable algorithm (keeps equal elements in the same order).
• In-place sorting (doesn’t require extra memory).

When to Use Insertion Sort in Kotlin

• For small data sets where performance isn’t critical.
• When you expect the data to be almost sorted.
• For educational purposes to build a strong foundation in sorting.

Conclusion

The Kotlin Insertion Sort algorithm is a simple yet powerful way to understand sorting from the ground up. While you’ll often rely on Kotlin’s built-in sorting functions in real-world applications, practicing with insertion sort sharpens your coding skills and deepens your understanding of algorithm design.

By walking through the logic step by step and testing with code, you’ve now got a solid grasp of how insertion sort works in Kotlin.