Как решить задачу со слиянием двух отсортированных массива в один отсортированный с помощью дополнительного массива

«Как решить задачу со слиянием двух отсортированных массива в один отсортированный с помощью дополнительного массива» — вопрос из категории Алгоритмы и структуры данных, который задают на 23% собеседований Android Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Ответ

Для слияния двух отсортированных массивов можно использовать метод двух указателей. Создаем новый массив размером arr1.size + arr2.size, затем поочередно сравниваем элементы исходных массивов и записываем меньший в результирующий.

fun mergeSortedArrays(arr1: IntArray, arr2: IntArray): IntArray {
    val result = IntArray(arr1.size + arr2.size)
    var i = 0 // указатель для arr1
    var j = 0 // указатель для arr2
    var k = 0 // указатель для result

    while (i < arr1.size && j < arr2.size) {
        result[k++] = if (arr1[i] < arr2[j]) arr1[i++] else arr2[j++]
    }

    // Дописываем оставшиеся элементы
    while (i < arr1.size) result[k++] = arr1[i++]
    while (j < arr2.size) result[k++] = arr2[j++]

    return result
}

Сложность алгоритма: O(n+m), где n и m - длины массивов. Дополнительная память: O(n+m) для результирующего массива.