arrays - MergeSort 实现稳定性

Question

mergesort的实现会影响它的稳定性吗？

比如我们用数组来实现归并排序，是不是不如链表实现归并排序稳定？

Answer 1

大多数自上而下(递归)和自下而上(迭代)的数组或链表合并排序的实现都是稳定的。关键因素在于合并函数，只要合并函数在“右”元素之前移动相等的“左”元素，它就会稳定。比较可以是“左”元素<=“右”元素，或者在C++标准库的情况下，它只使用小于进行比较，它的比较是“右”元素<“左”元素，所以“左”元素如果它是 <= "right"元素，将会被移动。

另一个可能的问题是混合归并排序，它对一小组元素使用不稳定的排序方法。

一般来说，交换相邻元素的排序(如冒泡排序)通常是稳定的，而交换非相邻元素的排序(如快速排序)通常不稳定。