Алгоритм сортировки для использования в этом конкретном сценарии

Question

У меня есть два списка - назовем их детали и итоги .

Элементы в details имеют несколько элементов для каждого ключа, по которому сортируется список, как таковой:

КЛЮЧ1
КЛЮЧ1
KEY2
KEY2
KEY3
KEY3
KEY3
и т.д.

Элементы в итоги будут иметь каждый ключ только один раз, как таковой:

КЛЮЧ1
KEY2
KEY3
и т.д.

Оба списка уже отсортированы по ключу. Списки необходимо объединить, чтобы новый список содержал элементы details , за которыми следует соответствующий элемент из totals , например:

KEY1 (это от детали )
KEY1 (это от детали )
KEY1 (это из итого ) и т.д.

Какой алгоритм сортировки обеспечит наилучшую производительность в этом сценарии?

(честно говоря, я просто собираюсь изменить код так, чтобы строка из totals создавалась и вставлялась при создании списка details , это это больше академический вопрос)

Answer 1

Если вы хотите объединить два списка в один, и они уже отсортированы, вам не следует прибегать к помощи.

Простое слияние будет сделано следующим образом. Это при условии, что ваши предположения верны, и нет «голых» подробностей или итоговых строк (подробностей без итогов или итогов без подробностей). Если они есть, вам понадобится дополнительный код, чтобы справиться с этим, но принцип тот же.

Get first detail-list
Get first total-list

While total-list not finished:
    If detail-list.key > total-list.key:
        Output total-list
        Get next total-list
        Next while
    Output detail-list
    Get next detail-list