Как слить два отсортированных массива в один отсортированный

Алгоритм слияния двух отсортированных массива

Слияние двух отсортированных массивов в один — классическая задача, часто встречающаяся в алгоритмах сортировки, таких как Merge Sort, и в различных практических сценариях (например, объединение отсортированных списков данных). Основной подход использует метод «двух указателей» (Two Pointers), который эффективен и имеет линейную временную сложность.

Основная идея алгоритма

Мы имеем два массива, arr1 и arr2, уже отсортированные по возрастанию. Цель — создать новый массив result, который будет содержать все элементы из обоих исходных массивов, также в отсортированном порядке. Алгоритм работает следующим образом:

1. Инициализируются два указателя (индексы), i и j, установленные на 0 (начало каждого массива).
2. Создается новый массив result размером arr1.length + arr2.length.
3. Используется третий указатель k для заполнения массива result.
4. В цикле сравниваются элементы arr1[i] и arr2[j]. Меньший из них помещается в result[k], и соответствующий указатель (i или j) увеличивается на 1.
5. Указатель k также увеличивается после каждого добавления.
6. Когда один из исходных массивов полностью обработан, остаток второго массива просто копируется в result.

Реализация на Kotlin

Ниже представлена реализация алгоритма на Kotlin, типичном языке для разработки под Android.

fun mergeSortedArrays(arr1: IntArray, arr2: IntArray): IntArray {
    val m = arr1.size
    val n = arr2.size
    val result = IntArray(m + n)

    var i = 0 // Указатель для arr1
    var j = 0 // Указатель для arr2
    var k = 0 // Указатель для result

    // Основной цикл сравнения и слияния
    while (i < m && j < n) {
        if (arr1[i] <= arr2[j]) {
            result[k] = arr1[i]
            i++
        } else {
            result[k] = arr2[j]
            j++
        }
        k++
    }

    // Копирование остатка из arr1, если он есть
    while (i < m) {
        result[k] = arr1[i]
        i++
        k++
    }

    // Копирование остатка из arr2, если он есть
    while (j < n) {
        result[k] = arr2[j]
        j++
        k++
    }

    return result
}

Ключевые характеристики алгоритма

• Временная сложность: O(m + n), где m и n — размеры массивов. Алгоритм проходит каждый элемент только один раз.
• Пространственная сложность: O(m + n) для создания нового массива результата. Если бы мы сливали массивы прямо в один из исходных (при условии, что он имеет достаточный размер), сложность могла бы быть O(1), но это менее типичный сценарий.
• Устойчивость: Если в массивах есть равные элементы, порядок их появления сохраняется (arr1[i] <= arr2[j] гарантирует, что элемент из первого массива будет помещен первым).

Пример использования и вариации

fun main() {
    val array1 = intArrayOf(1, 3, 5, 7)
    val array2 = intArrayOf(2, 4, 6, 8, 10)
    val mergedArray = mergeSortedArrays(array1, array2)
    println(mergedArray.joinToString()) // Вывод: 1, 2,我们用「合并两个已排序数组」这个中文术语。 3, 4, 5, 6, 7, 8, 10
}

В Android разработке этот алгоритм может применяться не только для сортировки, но и, например, для объединения отсортированных списков данных из разных источников (локальной базы и сетевого ответа) перед отображением в RecyclerView. Также существуют вариации:

• Слияние без создания нового массива (in-place), если один массив имеет достаточный «буфер».
• Слияние ArrayList или других коллекций.
• Рекурсивное слияние в алгоритме Merge Sort.

Понимание этого фундаментального алгоритма важно для разработчика, так как оно демонстрирует умение эффективно работать с данными и оптимизировать производительность, что критично в мобильной разработке, где ресурсы часто ограничены.