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

Question

在看《算法》第4版第2章第2.2.10题时遇到了一个问题。书上说fast merge算法结果不稳定，找不到证据that.Help我，谢谢！

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++];
}

我找不到不稳定的结果，我怎么会这样？

Answer 1

使 "equal" 个元素保持相同顺序的排序算法被认为是稳定的。因此 unstable 意味着：你有多个相等的元素，当你对整体 list/array 进行排序时，该排序的输出具有那些 equal元素（可能）以不同的顺序出现。

例如，假设您有一个人 class，并且实施平等以仅查看姓氏而忽略名字。

现在，假设您有两个 Person 对象，分别代表 "John Doe" 和 "Jane Doe"。它们按此顺序在您的未排序列表中。

稳定意味着：你总是以 "John Doe" 出现在 "Jane Doe" 之前结束。对于不稳定的排序，您没有这种保证。

换句话说：您需要创建一个至少具有两个属性的class。然后你需要定义 compareTo() 只依赖这两个属性之一。

然后您创建了一些 class 对象的示例列表，然后您进行了足够长的实验，直到找到一个示例，其中排序列表显示相同的对象改变了顺序。

换句话说：创建一个列表 (p1, p2, p3, p4, ...)，对其进行排序，然后寻找一个结果可能是... p4, p3 ... 虽然 p4和 p3 被认为是 "equal"。

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

创建一个 "generator"，它可以创建一些 class 对象的 "random" 对象，你稍后会对其进行排序（你倾斜生成器以确保你得到一堆 "equal"对象）
然后让框架测试底层"assertion"，排序前后"equal"对象的顺序不能改变。

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

Answer 2

证明排序算法不稳定只需要找到一个失败的地方。证明排序算法稳定会更加复杂。检查失败的一种方法是使用整数数组并将整数分成两部分，高 8 位作为伪随机值，低 24 位等于整数的索引（0 到 count-1）。然后运行排序，只用高8位进行比较，比如在C:

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

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

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

显然，这被称为 "fast" 合并排序的原因是，在进行合并时没有检查运行的结尾。左运行从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]，从原来右边的两个最高元素运行.在这种情况下，元素以相反的顺序复制。

虽然书上叫它快速归并排序，但是如果避免复制aux中的数据，而是根据递归的层次改变归并方向，速度会更快。对于自上而下，这可以通过递归调用中的一种类型复制和交换数组引用来完成，例如这个 wiki 示例：

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

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

自下而上的合并排序稍微快一些，因为它跳过了堆栈上索引的所有递归拆分和存储。在这种情况下，合并的方向基于合并通道。为了保持遍数均匀，可以提前检查奇数遍计数，并在开始第一个自下而上合并排序遍之前交换元素对。

Answer 3

为了证明算法的不稳定性，一个反例就足够了：让我们考虑对 4 个元素 A B C D 的数组进行排序所采取的步骤，这些元素比较等于 less 谓词。

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

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

How do you prove or illustrate that fast merge sort is an unstable algorithm?

java

algorithm

mergesort

array-algorithms