Рекурсивный MergeSort из двух массивов

Question

Я ставлю перед собой задачу написать код вручную для проведения собеседований, и я создал рекурсивную реализацию MergeSort на уровне ниже указанного.

Концепция заключается в том, чтобы взять два списка «alist» и «blist» и объединить / отсортировать их в список «clist».Предполагается, что списки отсортированы и имеют одинаковый размер перед объединением.

Как сделать так, чтобы исходный код (который, как я знаю, не работал должным образом) отражал код модели (работающий по назначению) с наименьшим количеством измененийвозможный?Знание степени моих ошибок очень поможет мне.

Оригинальный код:

alist = [1,5,8,9]
blist = [2,4,7,10]
clist = []
temp = []

def MergeSort(alist,blist):
    if len(alist) > 1:
        midpoint = len(alist)//2
        MergeSort(alist[midpoint:],alist[:midpoint])
    if len(blist) > 1:
        midpoint = len(blist)//2
        MergeSort(blist[midpoint:],blist[:midpoint])
    if alist[0] < blist[0]:
        temp[0] = alist[0]
        alist[0] = blist[0]
        blist[0] = temp[0]
        MergeSort(alist,blist)
    else:
        alist[len(alist)] = blist[len(blist)-1]
        MergeSort(alist,blist)
    if blist[0] == None:
        return alist

clist = MergeSort(alist,blist)
print(clist)

Код модели:

alist = [1,5,8,9]
blist = [2,4,7,10]

def MergeSort(alist, blist):
    clist = []
    if alist == [] and blist != []:
        return clist + blist

    if alist != [] and blist != []:
        if alist[0] <= blist[0]:
            clist.append(alist[0])
            clist = clist + MergeSort(alist[1:], blist)
        if alist[0] > blist[0]:
            clist.append(blist[0])
            clist = clist + MergeSort(alist, blist[1:])
    return clist

print(MergeSort(alist,blist))

Answer 1

Алгоритм состоит из двух частей

• Сортировка слиянием: сортировка списка
• Слияние: объединение двух уже отсортированных списков в один отсортированный список

Merge отсутствует в вашем коде.

Алгоритм:

MergeSort(A, B)
     1.1 MergeSort(first_half_of_A, second_half_A)
     // Now first_half_of_A and second_half_A are in sorted order independently   
     1.2 Merge(first_half_of_A, first_half_of_A)
     // Now A is fully sorted

     2.1 MergeSort(first_half_of_B, second_half_B)
     2.2 Merge(first_half_of_B, second_half_B)
     // Now B is fully sorted

     3. Merge(A, B)

Merge(A,B) прост, поскольку A и B уже отсортированы, считая, что они выбираютнаименьший элемент каждый раз.

def merge(alist,blist): 
    temp = list()
    i = 0
    j = 0

    while i < len(alist) and j < len(blist) :
        if  alist[i] < blist[j] :
            temp.append(alist[i])
            i += 1
        else:
            temp.append(blist[j])
            j += 1

    while i < len(alist): 
        temp.append(alist[i])
        i += 1

    while j < len(blist): 
        temp.append(blist[j])
        j += 1

    return temp

# Test case
assert merge([1,5,8,9], [1,2,3,4]) == [1, 1, 2, 3, 4, 5, 8, 9]

Теперь, наконец, MergeSort

def MergeSort(alist,blist):
    if len(alist) > 1:
        midpoint = len(alist)//2
        MergeSort(alist[midpoint:],alist[:midpoint])
        alist[:] = merge(alist[midpoint:], alist[:midpoint])
    if len(blist) > 1:
        midpoint = len(blist)//2
        MergeSort(blist[midpoint:],blist[:midpoint])
        blist[:] = merge(blist[midpoint:], blist[:midpoint])

    return merge(alist, blist)

# Test Case
assert MergeSort([1,5,8,9], [2,4,7,10]) == [1, 2, 4, 5, 7, 8, 9, 10]

# Testing
import numpy as np
for i in range(1000):
    a = np.random.rand(100)
    b = np.random.rand(100)
    c = np.append(a,b)
    assert np.sum(MergeSort(a,b)-np.sort(c)) == 0