J. Слияние

Напишите функцию merge, которая принимает два отсортированных по возрастанию кортежа целых чисел, а возвращает один из всех переданных чисел.

Примечание

Ваше решение должно содержать только функции.
В решении не должно быть вызовов требуемых функций.
В этой задаче отключены стандартные сортировки

Пример

Ввод

result = merge((1, 2), (3, 4, 5))

Вывод

result = (1, 2, 3, 4, 5)

Ввод

result = merge((7, 12), (1, 9, 50))

Вывод

result = (1, 7, 9, 12, 50)

Решение

Задание представляет собой часть одного из самых эффективных алгоритмов сортировки – сортировка слиянием. Нам нужно написать алгоритм заключительной части – слияние двух отсортированных списков.

Решение достаточно простое.

Сравниваем текущие (на первом этапе первые) элементы обоих списков и добавляем в новый список-результат наименьшее из двух чисел. Берем следующий за использованным элемент из соответствующего списка и повторяем процесс до тех пор, пока в одном из списков не закончатся элементы.

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

Ниже представлено два решения – первое интуитивно более простое, с удалением использованных элементов из списка. Это решение очень наглядное, но неэффективное с точки зрения производительности, так как удаление элементов из списков во-первых портит входные данные, а во-вторых операция удаления первого элемента списка относительно дорогая, c точки зрения использования вычислительных ресурсов, операция.

Вопреки заявлениям Яндекса, по состоянию на 16 января 2024 года для решения задачи можно воспользоваться методом sort(), что напрочь убивает всю пользу от самостоятельного решения этой задачи.

# Вариант с удалением элементов из списков

def merge(sequence_1, sequence_2):
    queue_1 = list(sequence_1)
    queue_2 = list(sequence_2)
    sequence = []
    while queue_1 and queue_2:
        if queue_1[0] > queue_2[0]:
            sequence.append(queue_2.pop(0))
        else:
            sequence.append(queue_1.pop(0))
    sequence.extend(queue_1)
    sequence.extend(queue_2)
    return tuple(sequence)

# Вариант с индексами элементов списков

def merge(sequence_1, sequence_2):
    pos1 = 0
    pos2 = 0
    sequence = []
    while pos1 < len(sequence_1) and pos2 < len(sequence_2):
        if sequence_1[pos1] > sequence_2[pos2]:
            sequence.append(sequence_2[pos2])
            pos2 += 1
        else:
            sequence.append(sequence_1[pos1])
            pos1 += 1
    sequence.extend(sequence_1[pos1:])
    sequence.extend(sequence_2[pos2:])
    return tuple(sequence)