Merge Sort (Divide and Conquer)

Merge two ordered runs with one invariant

Merge sort recursively orders halves, then merges them. The output prefix always contains the smallest remaining values from both runs.

Copy codefun mergeSort(values: List<Int>): List<Int> {
    if (values.size < 2) return values
    val middle = values.size / 2
    val left = mergeSort(values.subList(0, middle))
    val right = mergeSort(values.subList(middle, values.size))
    val result = ArrayList<Int>(values.size)
    var i = 0
    var j = 0
    while (i < left.size && j < right.size) {
        if (left[i] <= right[j]) result.add(left[i++]) else result.add(right[j++])
    }
    while (i < left.size) result.add(left[i++])
    while (j < right.size) result.add(right[j++])
    return result
}

Choosing the left value on ties preserves stability. Assuming efficient indexed list access, time is O(n log n). This educational implementation allocates intermediate lists; production array variants can reuse a buffer to reduce allocation churn.

Exercise

Compare against sorted() on random small inputs, including duplicates and negative values. Explain why the leftover loops are necessary after one half is exhausted.

Check: distinguish peak live memory from total allocations over all recursion levels.

Further reading: Merge sort