Is this considered a stable sort method?

Question

Currently trying to create a merge sort and I believe it's missing something to be stable. compare.js

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

My code so far:

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

My input:

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

After running the code, this is what's returned.

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

My result is close but my first name values are a little of. What I should receive:

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

Am I missing an edge case?

Answer 1

Mergesort is a stable sort algorithm but your implementation is not stable because of a small mistake in the merge function: if (comparison < 0) selects the element from the right half instead of the left half if these elements compare equal. You should instead write:

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