如何证明或说明快速归并排序是一种不稳定的算法？

Question

当我读《算法》第二章问题2.2.10时，遇到了一个困扰。这本书说快速合并算法的结果是不稳定的，但我找不到证据。请帮忙解答，谢谢！

public static void sort(Comparable[] a, int lo, int hi){
    if hi <= lo {
    return;
    }
    int mid = lo + (hi - lo) / 2;
    sort(a, lo, mid);
    sort(a, mid+1, hi);
    merge(a, lo, mid, hi);
}

// Why is the result of this sort not stable
private static void merge(Comparable[] a, int lo, int mid, int hi) { 
   for (int i = lo; i <= mid; i++)
      aux[i] = a[i]; 

   for (int j = mid+1; j <= hi; j++)
      aux[j] = a[hi-j+mid+1];

   int i = lo, j = hi; 
   for (int k = lo; k <= hi; k++) 
      if (less(aux[j], aux[i])) a[k] = aux[j--];
      else                      a[k] = aux[i++];
}

我找不到结果不稳定的原因，怎么才能得到稳定的结果？

- cheny

---

好的，那么我的回答应该涵盖了你在作业上取得进展所需的一切。如果你需要更多信息，请给我留言，否则请考虑在某个时候接受这个答案。 - GhostCat

Answer 1

保持“相等”元素在同一顺序的排序算法被认为是稳定的。因此，不稳定的意思是：您有多个相等的元素，并且当您对整体列表/数组进行排序时，该排序的输出会使那些相等的元素（可能）以不同的顺序出现。

例如，假设您有一个Person类，平等性仅实现在姓氏上，并忽略名字。

现在，假设你有两个Person对象，代表“John Doe”和“Jane Doe”。它们以这种顺序出现在您未排序的列表中。

稳定的意思是：您总是以“John Doe”出现在“Jane Doe”之前结束。使用不稳定的排序，您不能保证这一点。

换句话说：您需要创建一个具有至少两个属性的类。然后，您需要定义compareTo()仅依赖于其中一个属性。

然后，您创建该类的一些示例对象列表，然后进行足够长时间的实验，直到找到一个示例，其中排序后的列表显示相等的对象已更改顺序。

换句话说：创建一个列表(p1, p2, p3, p4, ...)，对其进行排序，然后查看结果，可能会说...p4,p3...尽管p4和p3被认为是“相等”。

最后：这实际上是使用一些属性基础测试框架（例如QuickCheck）的非常好的用例。使用这样的框架，您需要：

• 创建一个“生成器”，可以创建某个类的“随机”对象，您稍后对其进行排序（其中您偏斜生成器以确保从中获取一堆“相等”对象）
• 然后让框架测试底层的“断言”，即“相等”对象在排序前后的顺序必须不变。

然后让框架发挥它的魔力...

- GhostCat

Answer 2

为了证明算法的不稳定性，只需要一个反例：考虑对4个元素 A B C D 进行排序，这些元素在 less 谓词中相等。

• sort(a, 0, 3) 对两个子数组进行递归：
• sort(a, 0, 1) 再次递归
• sort(a, 0, 0) 立即返回
• sort(a, 1, 1) 立即返回
• merge(a, 0, 0, 1) 不改变 A B 的顺序
• sort(a, 2, 3) 递归到
• sort(a, 2, 2) 立即返回
• sort(a, 3, 3) 立即返回
• merge(a, 2, 2, 3) 不改变 C D 的顺序
• merge(a, 0, 1, 3) 将项目 A B C D 按顺序 A B D C 复制到 t 中，然后合并循环中的所有比较都为 false，因此复制回 a 的元素顺序相同，从 t[i++] 复制： A B D C，证明了排序算法的不稳定性，即：相等元素的相对顺序不被保留。

- chqrlie

Answer 3

证明一个排序算法是不稳定的只需要找到一个失败案例。证明一个排序算法是稳定的则需要更多的工作。检查失败的一种方法是使用一个整数数组并将整数分成两部分，上8位作为伪随机值，下24位等于整数的索引（0到count-1）。然后运行排序，仅使用上8位进行比较，例如在C语言中：

    if((b[j]&0xff000000) < (b[i]&0xff000000)) ...

排序完成后，使用所有32位检查数组是否有序。

使用此方法，我能够确认这种变体的归并排序是不稳定的。

显然，这种被称为“快速”归并排序的原因是，在执行合并时没有检查运行结束。左侧运行按照从lo到mid的正向顺序复制到aux[]中，而右侧运行则按照从hi到mid+1的反向顺序复制到aux[]中。然后，合并从两端（lo和hi）开始，并朝着中间（mid和mid+1）工作，左侧运行使用i从lo到mid向前移动，右侧运行使用j从hi到mid+1向后移动。由于没有检查运行结束，i可能会增加到mid以上（潜在的稳定性问题），或者j可能会减少到mid+1以下（不是稳定性问题）。当i增加到mid以上且aux[mid+1] == aux[mid+2]时，即来自原始右侧运行的最高两个元素时，稳定性会被破坏。在这种情况下，元素按相反的顺序复制。

尽管这本书称之为快速归并排序，但避免在辅助数组中复制数据，并根据递归的层级改变归并的方向会更快。对于自顶向下的方法，可以通过一种类型的复制和在递归调用中交换数组引用来实现，就像维基百科上的例子一样。

https://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation

可以使用一对相互递归的函数来避免初始复制，其中一个以a[]中的结果结束，另一个以b[]中的结果结束。

稍微快一点的是自底向上的归并排序，因为它跳过了所有递归分割和在堆栈上存储索引的步骤。在这种情况下，合并方向基于合并传递。为了保持传递次数偶数，可以提前检查奇数传递计数，并在开始第一个自底向上的归并排序传递之前交换成对元素。

- rcgldr