Код Mergesort зависает

Question

Я пытаюсь реализовать слияние. У меня есть рабочая подфункция слияния, которая работает с отсортированными списками, и мне просто нужно правильно управлять слиянием всех списков.

def mergesort(alist):
    alist = [[i] for i in alist]

    def merge(clist, dlist): #assume inputs are sorted
        merged = []
        while True:
            if len(clist) == 0:
                return merged + dlist
            elif len(dlist) == 0:
                return merged + clist
            elif clist[0] < dlist[0]:
                merged.append(clist[0])
                del clist[0]
            elif clist[0] > dlist[0]:
                merged.append(dlist[0])
                del dlist[0]            
        return merged

    while True:
        if len(alist) % 2 == 0 and len(alist) > 2:
            alist = [merge(alist[2*i], alist[2 * i + 1]) for i in range(int(len(alist)/2))]
        elif len(alist) == 2:
            print('ayyy')
            alist = merge(alist[0], alist[-1])
            return alist
        elif len(alist) % 2 == 1 and len(alist) > 1:
            tag = alist[-1]
            del alist[-1]
            alist = [merge(alist[2 * i], alist[2 * i + 1]) for i in range(int(len(alist)/2))]
            alist.append(tag)
        else:
            return alist


print(mergesort([10, 5, 8, 16, 258, 11, 1, 20, 489, 10, 5, 3, 12]))

Функция работает нормально, пока не дойдет до последних двух списков. Он печатает «ayyy», что означает, что он вошел в первое утверждение elif, а затем больше ничего не делает. Программа не завершается, она просто вращается. Отладчик показывает, что значение alist также не обновляется.

Answer 1

Я не мог удержаться от соблазна переписать merge, используя итераторы, таким образом, чтобы не изменять списки аргументов.

def merge(clist, dlist):
    "Merges two sorted lists into one still sorted list"
    if not clist:      # Trivial empty cases
        return dlist
    if not dlist:
        return clist
    cs = iter(clist)   # Iterators produce each item only once
    ds = iter(dlist)
    c = next(cs)
    d = next(ds)
    result = []
    while True:
        if c <= d:
            result.append(c)
            try:
                c = next(cs)
            except StopIteration:  # exhausted c before d
                result.append(d)
                result.extend(ds)
                return result
        else:  # c > d
            result.append(d)
            try:
                d = next(ds)
            except StopIteration:
                result.append(c)
                result.extend(cs)
                return result

Ясно, что это можно объединить, рассматривая списки одинаково. Эта конкретная версия предпочитает сначала размещать элементы из первого списка.

Обратите внимание, что del somelist[0] является самой дорогой операцией удаления элемента; он перемещает все записи, кроме первой. deque s поддерживает более эффективный метод popleft (но более дорогостоящий, когда вы создаете много небольших экземпляров, а слияние слиянием делает).

Answer 2

У вас есть только одна маленькая ошибка, потому что вы не имеете дело с равными элементами в merge. Вот небольшое исправление:

if len(clist)==0:
    return merged+dlist
elif len(dlist)==0:
    return merged+clist
elif clist[0]<dlist[0]:
    merged.append(clist[0])
    del clist[0]
elif clist[0]>dlist[0]:
    merged.append(dlist[0])
    del dlist[0]
else: # clist[0]==dlist[0]
    merged.append(clist[0])
    merged.append(dlist[0])
    del clist[0]
    del dlist[0]