Оптимизация или настройка следующей реализации для Merge Sort 3 way

Question

Я недавно играл с алгоритмами сортировки, и после прикосновения к алгоритму сортировки слиянием я хотел попытаться реализовать вспомогательную функцию слияния алгоритма, используя 3 отсортированных списка, а не 2.

Моя текущая реализация работает, но мне было интересно, если есть какой-то способ настроить его или реализовать по-другому, чтобы заставить его работать быстрее.

Вот код:

def merge_three(l1, l2, l3):
    """This function returns a sorted list made out of the three
    given lists.

    >>> merge_three([9, 29], [1, 7, 15], [8, 17, 21])
    [1, 7, 8, 9, 15, 17, 21, 29]
    """

    index1, index2, index3 = 0, 0, 0
    to_loop = len(l1) + len(l2) + len(l3)
    sorted_list = []

    i = 0
    while i < to_loop:
        advance = 0
        value = float("inf")

        if index1 < len(l1) and l1[index1] <= value:
            advance = 1
            value = l1[index1]

        if index2 < len(l2) and l2[index2] <= value:
            advance = 2
            value = l2[index2]

        if index3 < len(l3) and l3[index3] <= value:
            advance = 3
            value = l3[index3]

        sorted_list.append(value)

        if advance == 1:
            index1 += 1
        elif advance == 2:
            index2 += 1
        else:
            index3 += 1

        i += 1
    return sorted_list

Спасибо:)

Answer 1

Думая о более общей функции слияния, мы получаем более простой дизайн. Предположим, вы хотите написать функцию, которая берет список отсортированных списков и объединяет все списки. Идея проста: найти список с наименьшим элементом, удалить его, переместить в список результатов, удалить список из списка, когда он пуст, и выполнять итерацию, пока сам список не будет пустым.

Один из подходов:

def merge(lists):
  result = []

  while len(lists):
    (index, value) = min(enumerate(i[0] for i in lists), key=lambda x: x[1])
    result.append(lists[index].pop(0))
    if len(lists[index]) == 0:
      lists.pop(index)

  return result