这被认为是一种稳定的排序方法吗？

Question

目前正在尝试创建合并排序，我认为它缺少一些稳定的东西。 compare.js

function compare(left, right) {
  return left - right;
}

到目前为止我的代码：

function merge(compare, left, right) {
  let sorted = [];

  while (left.length && right.length) {
    const comparison = compare(left[0], right[0]);

    if (comparison < 0) {
      sorted.push(left.shift());
    } else {
      sorted.push(right.shift());
    }
  }
  return sorted.concat(left, right);
}

function sort(compare, elements) {
  if (Array.isArray(elements)) {
    if (elements.length <= 1) {
      return elements;
    }

    const middle = Math.floor(elements.length / 2);

    const leftElements = elements.slice(0, middle);
    const rightElements = elements.slice(middle);

    const leftSorted = sort(compare, leftElements);
    const rightSorted = sort(compare, rightElements);

    return merge(compare, leftSorted, rightSorted);
  }
  return elements;
}

我的输入：

[
  { firstName: "b", lastName: "c" },
  { firstName: "a", lastName: "b" },
  { firstName: "a", lastName: "a" },
  { firstName: "c", lastName: "b" },
  { firstName: "b", lastName: "b" },
  { firstName: "a", lastName: "c" },
]

在运行代码之后，这是返回的内容。

[
  { firstName: 'a', lastName: 'a' },
  { firstName: 'b', lastName: 'b' },
  { firstName: 'c', lastName: 'b' },
  { firstName: 'a', lastName: 'b' },
  { firstName: 'a', lastName: 'c' },
  { firstName: 'b', lastName: 'c' }
]

我的结果很接近，但我的名字值有点。我应该得到什么：

[
  { firstName: "a", lastName: "a" },
  { firstName: "a", lastName: "b" },
  { firstName: "c", lastName: "b" },
  { firstName: "b", lastName: "b" },
  { firstName: "b", lastName: "c" },
  { firstName: "a", lastName: "c" },
]

我是否遗漏了一个边缘案例？

Answer 1

Mergesort 是一种稳定的排序算法，但由于 merge 函数中的一个小错误，您的实现不稳定：if (comparison < 0) 从右半部分而不是左半部分选择元素，如果这些元素比较相等。你应该改为写：

    if (comparison <= 0) {
        sorted.push(left.shift());
    } else {
        sorted.push(right.shift());
    }

这被认为是一种稳定的排序方法吗？

Is this considered a stable sort method?

javascript

sorting

algorithm

mergesort