How can I implement a stable QuickSort algorithm in JavaScript?

General Discussions
1

How can I implement a stable QuickSort algorithm in JavaScript? I’m looking for a way to write a reliable and effective implementation of the QuickSort algorithm while ensuring it remains stable. What is the best approach to achieve a stable quicksort in JavaScript?

2

One way to achieve stability is by using an auxiliary array to hold the sorted elements during the partitioning phase. This helps maintain the relative order of equal elements.

Here’s an example:

function stableQuickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[arr.length - 1];
const left = [];
const right = [];
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...stableQuickSort(left), pivot, ...stableQuickSort(right)];
}
const array = [3, 1, 4, 1, 5, 9, 2];
console.log(stableQuickSort(array)); // Output: [1, 1, 2, 3, 4, 5, 9]