c - 自下而上归并排序的意外困境

Question

我最近刚刚读完自下而上合并排序的要点，在我看来，这是有道理的，但是当我想到如何实现时，它让我有点困惑。

我知道我们首先要合并相邻的元素对，但是在合并元素之前我们如何比较元素的大小？这最终不会成为一个 n^2 算法吗？

例如:

假设我有一个这样的数组:

int a[6] = {1,3,2,6,8,7};

然后我将其拆分为大小 1(不是真正拆分，而是查看我认为的索引)

{1}{3}{2}{6}**{8}{7}**

之后就变成这样了:

{1,3}{2,6}**{7,8}**<<<<<<<< I am assuming we are using an if statement to arrange
switching 7 and 8 in the merge process only takes O(n)

但是，

如何在下一次传递中进行比较:

**{1,2,3,6}**{7,8}   >>>> Wouldn't I need a nested for loop to compare and sort?

在我读到的所有示例中，他们没有解释如何设法比较它，他们只是说合并它并显示 2 个子数组神奇地自行排序的图片。我正在用 C 语言处理这个问题，我需要一些指导来指导如何在合并时按顺序排列它。除了合并后使用 O(n^2) 嵌套 for 循环之外，我想不出任何其他方式对其进行排序。如果有人能告诉我如何做到这一点，那么我会一如既往地高兴!

我想要得到的是，如果我使用 n^2 算法排序，它不会是 OlogN。

Answer 1

这是来自 Wikipedia's Merge Sort Implementation 的自下而上合并:

BottomUpMerge(int A[], int iLeft, int iRight, int iEnd, int B[])
{
    int i0 = iLeft;
    int i1 = iRight;
    int j;

    /* While there are elements in the left or right lists */
    for (j = iLeft; j < iEnd; j++) {
        /* If left list head exists and is <= existing right list head */
        if (i0 < iRight && (i1 >= iEnd || A[i0] <= A[i1]))
        {
            B[j] = A[i0];
            i0 = i0 + 1;
        }
        else
        {
            B[j] = A[i1];
            i1 = i1 + 1;
        }
    }
}