Итеративная сортировка слиянием?

Question

Мне известен классический рекурсивный подход к сортировке чего-либо путем слияния.Это дает O(n * log(n)) сложность, которая может быть более или менее легко показана через рекуррентное отношение.

Я пытался переопределить сортировку слиянием итеративным способом:

def atomize(l):
    return list(
        map(
            lambda x: [x],
            l if l is not None else []
        )
    )

def merge(l, r):
    res = []
    while (len(l) + len(r)) > 0:
        if len(l) < 1:
            res += r
            r = []
        elif len(r) < 1:
            res += l
            l = []
        else:
            if l[0] <= r[0]:
                res.append(l.pop(0))
            else:
                res.append(r.pop(0))
    return res

def iter_merge_sort(l):
    atoms = atomize(l) # O(n)
    while len(atoms) > 1: # O(n - 1)
        atoms.append(merge(atoms.pop(0), atoms.pop(0)))
    return atoms[0]

... и мне кажется, что я где-то ошибаюсь, но я не могу определить точное место.Проблема рекурсивной сортировки слиянием разбивает проблему, если список несортированных значений не сводится к списку синглетонов - отдельных элементов, которые можно сравнивать.Вот что делает atomize(...): данный список создает список списков-одиночек (порядок O(n)).

Очевидно, что merge(...) также равен O(n): на данный момент игнорировать отсутствие связанных списковиспользуются для объединения, это не важно здесь.

Наконец ... блок while в самом iter_merge_sort(...) занимает ровно n - 1 повторений, каждое из которых стоит максимум O(n).Поэтому я взял алгоритм O(n * log(n)) и «улучшил» его до (n - 1) * n ~ O(n * n).Где моя ошибка?

Answer 1

Ваш алгоритм полностью правильный.Проблема заключается в том, что вы используете list.pop(0) как способ удаления из очереди, что стоит O (n) в Python, поскольку все элементы после выталкиваемого элемента списка должны быть скопированы на предыдущие позиции.

Вы можете использовать collections.deque вместо списка, чтобы можно было использовать метод deque.popleft, который стоит O (1) :

from collections import deque

def atomize(l):
    return deque(
        map(
            lambda x: deque([x]),
            l if l is not None else []
        )
    )

def merge(l, r):
    res = deque()
    while (len(l) + len(r)) > 0:
        if len(l) < 1:
            res += r
            r = deque()
        elif len(r) < 1:
            res += l
            l = deque()
        else:
            if l[0] <= r[0]:
                res.append(l.popleft())
            else:
                res.append(r.popleft())
    return res

def iter_merge_sort(l):
    atoms = atomize(l) # O(n)
    while len(atoms) > 1: # O(n - 1)
        atoms.append(merge(atoms.popleft(), atoms.popleft()))
    return list(atoms[0])

так что:

iter_merge_sort([3,5,1,6,2,1])

возвращает:

[1, 1, 2, 3, 5, 6]