Stable Sorting in JavaScript

Objective: Efficiently sort an array of objects based on a key, maintaining consistency and stability.

Algorithm Recommendation: While many sorting algorithms exist, for your specific need of stability, consider implementing a modified version of a non-stable sorting algorithm such as QuickSort or MergeSort.

Stable Sorting Technique:

To ensure stability, add an additional criterion to the sort comparison function. Specifically, when comparing two equal elements, use their original positions in the input array as a tiebreaker. This will maintain the order of elements with the same key.

JavaScript Implementation:

const stableSort = (arr, key, order) => {
  // Get initial positions of elements
  const positions = arr.map((el, i) => i);

  // Sort using modified comparison function
  arr.sort((a, b) => {
    const keyA = a[key];
    const keyB = b[key];

    if (keyA === keyB) {
      // Fall back to position for stability
      return positions[a] - positions[b];
    }

    return order === "asc" ? keyA - keyB : keyB - keyA;
  });

  return arr;
};

Example Usage:

const arr = [
  { id: 1, value: 4 },
  { id: 2, value: 2 },
  { id: 3, value: 4 },
  { id: 4, value: 3 },
];

const sortedArr = stableSort(arr, "value", "asc");

// Output:
// [
//   { id: 2, value: 2 },
//   { id: 1, value: 4 },
//   { id: 3, value: 4 },
//   { id: 4, value: 3 },
// ]

By using this technique, you can obtain stable sorting even from non-stable sorting algorithms, making it suitable for your scenario of about 200-300 objects.