Kotlin Program to Merge Two Sorted Lists

You can merge two sorted lists in Kotlin by iterating through both lists with two pointers and adding the smaller element to a new list using code like fun mergeSortedLists(list1: List, list2: List): List which returns the merged sorted list.

Examples

Inputlist1 = [1, 3, 5], list2 = [2, 4, 6]

Output[1, 2, 3, 4, 5, 6]

Inputlist1 = [1, 2, 3], list2 = []

Output[1, 2, 3]

Inputlist1 = [5, 10, 15], list2 = [3, 6, 9, 12]

Output[3, 5, 6, 9, 10, 12, 15]

How to Think About It

To merge two sorted lists, think of walking through both lists at the same time. Compare the current items from each list and pick the smaller one to add to a new list. Move forward in the list where you took the item. Keep doing this until you reach the end of one list, then add all remaining items from the other list.

Algorithm

1

Start with two pointers at the beginning of each list.

2

Compare the elements at both pointers.

3

Add the smaller element to the result list and move that pointer forward.

4

Repeat until one list is fully traversed.

5

Add all remaining elements from the other list to the result.

6

Return the merged list.

Code

kotlin

fun mergeSortedLists(list1: List<Int>, list2: List<Int>): List<Int> {
    val merged = mutableListOf<Int>()
    var i = 0
    var j = 0
    while (i < list1.size && j < list2.size) {
        if (list1[i] < list2[j]) {
            merged.add(list1[i])
            i++
        } else {
            merged.add(list2[j])
            j++
        }
    }
    while (i < list1.size) {
        merged.add(list1[i])
        i++
    }
    while (j < list2.size) {
        merged.add(list2[j])
        j++
    }
    return merged
}

fun main() {
    val list1 = listOf(1, 3, 5)
    val list2 = listOf(2, 4, 6)
    val result = mergeSortedLists(list1, list2)
    println(result)
}

Output

[1, 2, 3, 4, 5, 6]

Dry Run

Let's trace merging list1 = [1, 3, 5] and list2 = [2, 4, 6] through the code

1

Initialize pointers and result

i = 0, j = 0, merged = []

2

Compare list1[i] and list2[j]

list1[0] = 1 < list2[0] = 2, add 1 to merged, i = 1

3

Compare next elements

list1[1] = 3 > list2[0] = 2, add 2 to merged, j = 1

4

Continue comparing

list1[1] = 3 < list2[1] = 4, add 3 to merged, i = 2

5

Continue comparing

list1[2] = 5 > list2[1] = 4, add 4 to merged, j = 2

6

Continue comparing

list1[2] = 5 < list2[2] = 6, add 5 to merged, i = 3

7

list1 exhausted, add remaining list2 elements

Add 6 to merged, j = 3

8

Return merged list

merged = [1, 2, 3, 4, 5, 6]

i	j	merged
0	0	[]
1	0	[1]
1	1	[1, 2]
2	1	[1, 2, 3]
2	2	[1, 2, 3, 4]
3	2	[1, 2, 3, 4, 5]
3	3	[1, 2, 3, 4, 5, 6]

Why This Works

Step 1: Two pointers track positions

We use i and j to track current positions in each list, so we compare elements in order.

Step 2: Compare and add smaller element

At each step, we add the smaller element to the merged list to keep it sorted.

Step 3: Add leftovers after one list ends

When one list finishes, we add all remaining elements from the other list because they are already sorted.

Alternative Approaches

Using Kotlin's built-in sorted merge

kotlin

fun mergeSortedLists(list1: List<Int>, list2: List<Int>): List<Int> = (list1 + list2).sorted()

fun main() {
    val list1 = listOf(1, 3, 5)
    val list2 = listOf(2, 4, 6)
    println(mergeSortedLists(list1, list2))
}

This is simpler but less efficient because it sorts the combined list instead of merging sorted lists directly.

Recursive merge

kotlin

fun mergeSortedLists(list1: List<Int>, list2: List<Int>): List<Int> {
    if (list1.isEmpty()) return list2
    if (list2.isEmpty()) return list1
    return if (list1.first() < list2.first()) {
        listOf(list1.first()) + mergeSortedLists(list1.drop(1), list2)
    } else {
        listOf(list2.first()) + mergeSortedLists(list1, list2.drop(1))
    }
}

fun main() {
    val list1 = listOf(1, 3, 5)
    val list2 = listOf(2, 4, 6)
    println(mergeSortedLists(list1, list2))
}

This uses recursion for clarity but can be less efficient and risk stack overflow on large lists.

Complexity: O(n + m) time, O(n + m) space

Time Complexity

The algorithm looks at each element from both lists once, so time grows linearly with the total number of elements.

Space Complexity

A new list is created to hold all elements, so space grows linearly with the total number of elements.

Which Approach is Fastest?

The two-pointer merge is fastest because it avoids sorting the combined list, unlike the built-in sorted approach.

Approach	Time	Space	Best For
Two-pointer merge	O(n + m)	O(n + m)	Large sorted lists, efficient merging
Built-in sorted	O((n + m) log(n + m))	O(n + m)	Simple code, small lists
Recursive merge	O(n + m)	O(n + m)	Clear code, small lists, but risk stack overflow