Merge двух отсортированных списков

Решение: Merge двух отсортированных списков

1. Базовая реализация O(n+m)

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

2. Обобщённая версия для Comparable типов

fun <T : Comparable<T>> mergeSortedLists(list1: List<T>, list2: List<T>): List<T> {
    val result = mutableListOf<T>()
    var i = 0
    var j = 0
    
    while (i < list1.size && j < list2.size) {
        val comparison = list1[i].compareTo(list2[j])
        if (comparison <= 0) {
            result.add(list1[i++])
        } else {
            result.add(list2[j++])
        }
    }
    
    result.addAll(list1.subList(i, list1.size))
    result.addAll(list2.subList(j, list2.size))
    
    return result
}

3. In-place версия для MutableList

fun mergeInPlace(list1: MutableList<Int>, list2: List<Int>) {
    var i = list1.size - 1
    var j = list2.size - 1
    var k = list1.size + list2.size - 1
    
    list1.addAll(list2.dropLast(list2.size))
    
    while (i >= 0 && j >= 0) {
        if (list1[i] >= list2[j]) {
            list1[k] = list1[i]
            i--
        } else {
            list1[k] = list2[j]
            j--
        }
        k--
    }
    
    while (j >= 0) {
        list1[k] = list2[j]
        j--
        k--
    }
}

4. Unit Тесты

class MergeSortedListsTest {
    @Test
    fun testMergeBothNonEmpty() {
        val result = mergeSortedLists(listOf(1, 3, 5), listOf(2, 4, 6))
        assertEquals(listOf(1, 2, 3, 4, 5, 6), result)
    }

    @Test
    fun testMergeOneEmpty() {
        assertEquals(listOf(1, 2, 3), mergeSortedLists(listOf(1, 2, 3), listOf()))
        assertEquals(listOf(1, 2, 3), mergeSortedLists(listOf(), listOf(1, 2, 3)))
    }

    @Test
    fun testMergeBothEmpty() {
        assertEquals(listOf(), mergeSortedLists(listOf(), listOf()))
    }

    @Test
    fun testMergeDuplicates() {
        val result = mergeSortedLists(listOf(1, 1, 2), listOf(1, 2, 3))
        assertEquals(listOf(1, 1, 1, 2, 2, 3), result)
    }

    @Test
    fun testMergeDifferentLengths() {
        val result = mergeSortedLists(listOf(1), listOf(2, 3, 4, 5))
        assertEquals(listOf(1, 2, 3, 4, 5), result)
    }

    @Test
    fun testMergeAllFirstSmaller() {
        val result = mergeSortedLists(listOf(1, 2, 3), listOf(4, 5, 6))
        assertEquals(listOf(1, 2, 3, 4, 5, 6), result)
    }

    @Test
    fun testMergeAllSecondSmaller() {
        val result = mergeSortedLists(listOf(4, 5, 6), listOf(1, 2, 3))
        assertEquals(listOf(1, 2, 3, 4, 5, 6), result)
    }

    @Test
    fun testMergeGenericStrings() {
        val result = mergeSortedLists(listOf("a", "c"), listOf("b", "d"))
        assertEquals(listOf("a", "b", "c", "d"), result)
    }

    @Test
    fun testMergeSingleElements() {
        val result = mergeSortedLists(listOf(1), listOf(2))
        assertEquals(listOf(1, 2), result)
    }

    @Test
    fun testMergeIdenticalLists() {
        val result = mergeSortedLists(listOf(1, 2, 3), listOf(1, 2, 3))
        assertEquals(listOf(1, 1, 2, 2, 3, 3), result)
    }
}

5. Анализ сложности

Временная сложность: O(n + m) где n и m размеры списков

• Каждый элемент посещается ровно один раз
• Сравнения выполняются линейное количество раз

Пространственная сложность: O(n + m)

• Результирующий список содержит n + m элементов
• In-place версия требует O(1) дополнительной памяти

Ключевые особенности

• Двухуказательный подход: Поддерживаем индексы в обоих списках
• Обработка пустых списков: Корректно работает со списками любого размера
• Дубликаты: Сохраняет порядок дубликатов используя <=
• Обобщённость: Generic версия работает с любыми Comparable типами
• Оптимальность: Достигает минимально возможной временной сложности
• Чистота кода: Использует addAll для оставшихся элементов

Применение в реальных проектах

Этот алгоритм используется в:

• Merge Sort
• Слиянии отсортированных массивов в БД запросах
• Слиянии результатов из разных источников данных
• Операциях над временными рядами в реальном времени