Performs stable sorting of an array, preserving the initial indexes of items when their values are the same.

Stable Sort in Javascript.js

// Instead of using an object with item and index properties, used an array with [item, index] values.
// This reduces the memory footprint and improves performance.
// Modified the .map() and .sort() functions to work with the array of [item, index] pairs.
// Used destructuring assignment in the .map() function to extract only the item value from each pair.

/**
 * Sorts an array in a stable manner using a custom compare function.
 *
 * @param {Array} arr - The array to be sorted.
 * @param {Function} compare - The compare function used to determine the order of elements.
 * @return {Array} The sorted array.
 */
function stableSort(arr, compare) {
    const sorted = arr.map((item, index) => [item, index]).sort((a, b) => compare(a[0], b[0]) || a[1] - b[1])

    return sorted.map(([item]) => item)
}



// Examples


const arr1 = [0, 11, 3, 2, 4, 6, 9, 7, 1, 8, 10]         //= [ 0, 11, 3, 2, 4, 6, 9, 7, 1, 8, 10 ]

const arr2 = [
    { height: 100, weight: 80 },
    { height: 90, weight: 90 },
    { height: 70, weight: 95 },
    { height: 100, weight: 100 },
    { height: 80, weight: 110 },
    { height: 110, weight: 115 },
    { height: 100, weight: 120 },
    { height: 70, weight: 125 },
    { height: 70, weight: 130 },
    { height: 100, weight: 135 },
    { height: 75, weight: 140 },
    { height: 70, weight: 140 },
]

const arr3 = Array(6)
    .fill()
    .map(() => Number(Math.random().toFixed(4)))        //= [0.6526, 0.22, 0.9751, 0.4973, 0.1021, 0.3966]


const alwaysEqual = () => 0
const ascending = (a, b) => a - b
const descending = (a, b) => b - a
const isUnmoved = (value, index) => value === arr3[index]


stableSort(arr1, () => 0)                              //= [ 0, 11, 3, 2, 4, 6, 9, 7, 1, 8, 10 ]
stableSort(arr2, (a, b) => a.height - b.height)        //= [ { height: 70, weight: 95 }, { height: 70, weight: 125 }, { height: 70, weigh ...
stableSort(arr3, alwaysEqual)                          //= [ 0.6526, 0.22, 0.9751, 0.4973, 0.1021, 0.3966 ]
stableSort(arr3, isUnmoved)                            //= [ 0.6526, 0.22, 0.9751, 0.4973, 0.1021, 0.3966
stableSort(arr3, ascending)                            //= [ 0.1021, 0.22, 0.3966, 0.4973, 0.6526, 0.9751 ]
stableSort(arr3, descending)                           //= [ 0.9751, 0.6526, 0.4973, 0.3966, 0.22, 0.1021 ]
stableSort(arr3.slice(), alwaysEqual).every(isUnmoved) //= true