4路合并排序挑战Python

Question

我试图编写一个MergeSort函数，将数组拆分为4个数组，而不是像常规的MergeSort那样拆分为2个

我试图遵循2路mergeSort并将其实现为4路，但我一直陷入递归调用中，我不明白问题出在哪里

我编写了一个merge_sort_4函数，它调用自身4次，merge4函数应该合并4个数组，而不是2个数组

我知道我班上的一些人通过对常规合并函数的3次调用就解决了这个问题，但我认为这有点忽略了这个挑战的要点

如果唯一的解决方法是使用常规合并，请告诉我，如果不是，请帮助我找到问题

这是我的密码

def merge_sort_4(lst, start, end):
    if start < end:
        quarter1 = (start + end) // 4
        quarter2 = (start + end) // 2
        quarter3 = (end - quarter1 - 1)

        merge_sort_4(lst, start, quarter1)
        merge_sort_4(lst, quarter1 + 1, quarter2)
        merge_sort_4(lst, quarter2 + 1, quarter3)
        merge_sort_4(lst, quarter3 + 1, end)

        merge4(lst, start, quarter1, quarter2, quarter3, end)


def merge4(lst, start, q1, q2, q3, end):
    first_q_list = lst[start:q1 + 1]
    sec_q_list = lst[q1 + 1:q2 + 1]
    third_q_list = lst[q2 + 1:q3 + 1]
    last_q_list = lst[q3 + 1:end + 1]

    first_q_list.append(float('inf'))
    sec_q_list.append(float('inf'))
    third_q_list.append(float('inf'))
    last_q_list.append(float('inf'))

    i = 0  # first sublist index
    j = 0  # sec sublist index
    m = 0  # third sublist index
    n = 0  # last sublist index

    for k in range(start, end + 1):
        if first_q_list[i] <= sec_q_list[j] and first_q_list[i] <= third_q_list[m] and first_q_list[i] <= last_q_list[
        n]:
            lst[k] = first_q_list[i]
            i += 1

        elif sec_q_list[j] <= third_q_list[m] and sec_q_list[j] <= last_q_list[n]:
            lst[k] = sec_q_list[j]
            j += 1

        elif third_q_list[m] <= last_q_list[n]:
            lst[k] = third_q_list[m]
            m += 1
        else:
            lst[k] = last_q_list[n]
            n += 1

提前感谢您的帮助

Answer 1

好的，我对这里可能有错误的地方有一些想法，但是你并没有给出太多你需要什么帮助的指示，所以首先我想为你指出正确的方向，让你自己来解决这个问题

在编写任何代码进入merge4和merge_sort_4之前，您能描述一下它们的先决条件和后决条件吗？也就是说，在调用其中一个参数之前，对于列表的状态和传递给它的参数，您要求什么是true？它的工作是什么？当它完成时，它保证做什么？start可以有什么值end可以有什么值

我希望您能够描述一些约束条件，例如0 <= start <= end < len(lst)用于调用merge_sort_4和0 <= start <= q1 <= q2 <= q3 <= end <= len(lst)用于调用merge4，并且merge4需要对四个子列表进行排序，并保证从list索引start到end的整个范围都是排序的

现在，这些事情真的是真的吗？你能用示例值浏览一下代码，看看会发生什么吗？您能否将断言添加到算法中，以捕获其中一个断言第一次不正确的情况？您能否在小块测试数据上分别测试算法片段，以查看它们的行为是否符合您的预期

试着看看你是否能自己找到答案，如果不能，我建议你开始找一个地方

我希望quarter1、quarter2和quarter3都应该在start到end的范围内，但我认为你的计算可能没有达到你的预期。试试start和end的不同值，看看你是否对结果感到惊讶

Answer 2

使用sentinel值（float（'inf'）时存在问题。考虑已经到达多个运行结束时的情况，例如当FixSyqQList[i]＝SeCyqQList[j]=浮点（“IF”），在这种情况下，FrestyQqList[I]中的浮点（“IF”）被复制到LST[K]，并且 I EME>递增超过FixtQqList[]结尾。

每次复制元素时，代码都需要检查是否到达运行的末尾，如果是，则下拉到剩余运行的3路合并。稍后将下降到双向合并，最后是剩余一次运行的其余部分的副本

代码可以被改进，考虑到TieldQuyList[]或LaSTiqqLST[]具有最小元素的情况，得到6个比较以得到这些情况。通过使用嵌套的if+else，可以将任何路径上的比较减少到3次，以确定哪个运行具有最小的元素。3路合并查找a、b、c中最小值的示例，对于3种可能情况中的任何一种，仅进行2次比较：

    if(a <= b)
        if(a <= c)
            a is smallest
        else
            c is smallest
    else
        if(b <= c)
            b is smallest
        else
            c is smallest

---

链接到4路自顶向下混合合并排序+插入排序（用于小规模运行）的java示例。我没有费心把它移植到Python上，因为Python太慢了，而且由于Python是一种解释性语言，4路合并排序在Python中可能比2路慢（在编译语言中，4路比2路快15%）

How can I implement the Merge Sort algorithm with 4-way partition without the error ArrayIndexOutOfBoundsException?