13.4.3 Функции с возвратом значения. Часть 1

Слияние двух отсортированных списков

Слияние двух отсортированных списков в один — важная задача в информатике. Она естественно возникает при сортировке списков с использованием сортировки слиянием.

Пусть даны два отсортированных по возрастанию списка чисел list1 и list2:

list1 = [3, 10, 11, 12, 47, 57, 58, 63, 77, 79, 80, 95]
list2 = [0, 11, 12, 20, 24, 26, 47, 48, 53, 65, 70, 81, 84, 84, 90]

Простейшее решение задачи слияния списков использует списочный метод sort():

def merge(list1, list2):
    result = list1 + list2   # создаем результирующий список
    result.sort()            # сортируем список встроенным методом sort()
    return result            # возвращаем отсортированный список


list1 = [3, 10, 11, 12, 47, 57, 58, 63, 77, 79, 80, 95]
list2 = [0, 11, 12, 20, 24, 26, 47, 48, 53, 65, 70, 81, 84, 84, 90]
list3 = merge(list1, list2)  # вызываем функцию слияния двух отсортированных списков

print(list3)

Приведённый выше код выводит:

[0, 3, 10, 11, 11, 12, 12, 20, 24, 26, 47, 47, 48, 53, 57, 58, 63, 65, 70, 77, 79, 80, 81, 84, 84, 90, 95]

И хотя функция merge() полностью справляется со своей задачей, она абсолютно не учитывает то, что два списка list1 и list2 уже отсортированы.

Быстрое слияние двух отсортированных списков в один

Пусть мы имеем два уже отсортированных по возрастанию списка list1 и list2.

Алгоритм быстрого слияния следующий:

1. Создаем численные указатели p1 = 0 и p2 = 0 на начала обоих списков list1 и list2 соответственно;
2. На каждом шаге берем меньший из двух элементов list1[p1] и list2[p2];
3. Записываем его в результирующий список; 
4. Увеличиваем на $1$ указатель на первый элемент списка (p1 или p2), из которого был взят элемент;
5. Когда один из начальных списков закончился, добавляем все оставшиеся элементы второго списка в результирующий список.

def quick_merge(list1, list2):
    result = []

    p1 = 0  # указатель на первый элемент списка list1
    p2 = 0  # указатель на первый элемент списка list2

    while p1 < len(list1) and p2 < len(list2):  # пока не закончился какой-нибудь из списков
        if list1[p1] <= list2[p2]:
            result.append(list1[p1])
            p1 += 1
        else:
            result.append(list2[p2])
            p2 += 1

    if p1 < len(list1):   # прицепление остатка
        result += list1[p1:]
    else:                 # иначе прицепляем остаток другого списка
        result += list2[p2:]
    
    return result

Приведённый ниже код:

list1 = [3, 10, 11, 12, 47, 57, 58, 63, 77, 79, 80, 95]
list2 = [0, 11, 12, 20, 24, 26, 47, 48, 53, 65, 70, 81, 84, 84, 90]
list3 = quick_merge(list1, list2)
print(list3)

выводит:

[0, 3, 10, 11, 11, 12, 12, 20, 24, 26, 47, 47, 48, 53, 57, 58, 63, 65, 70, 77, 79, 80, 81, 84, 84, 90, 95]