Sort an array based on a comparison function that can say "order is flexible" for some pairs.

sort_w_partial_info.js

// This will sort the values in `inputArr` according to the comparison data
// provided by calls to `inputCmp()`, which is expected to return the values '='
// (a string), '<', '>', or null; where a null indicates that the comparison
// value is undetermined, and that those two elements may go in any order.
// This function attempts to reduce the number of calls to inputCmp() in several
// ways:
//  * It memorizes given return values.
//  * It assumes that if a < b then also b > a (otherwise what is happening?).
//  * It builds a tree to infer transitive comparisons, and tries to maximize
//    the use of that tree.
export function sortWithPartialInfo(inputArr, inputCmp) {

    // 1. Set up memoization for inputCmp().

    // This serves to both memorize results as well as to allow us to treat the
    // input as an array of integers, although inputArr may have any types.
    const cache = {};
    function cmp(a, b) {
        let key = a + ':' + b;
        let val = cache[key];
        if (val !== undefined) return val;

        let result = (a === b) ? '=' : inputCmp(inputArr[a], inputArr[b]);
        cache[key] = result;

        let otherKey = b + ':' + a;
        let otherResult = result;
        if (result === '<') otherResult = '>';
        if (result === '>') otherResult = '<';
        cache[otherKey] = otherResult;

        return result;
    }

    // 2. Sort `arr`, using the memoized comparison function cmp().

    let arr     = inputArr.map((e, i) => i);
    let sorted  = [];
    let min     = arr[arr.length - 1];
    let cmpTree = {[min]: []}

    while (arr.length > 0) {

        let xIdx = -1;
        while (true) {

            xIdx++;
            if (xIdx == arr.length) {
                sorted.push(min);
                arr.splice(arr.indexOf(min), 1);
                for (let i = 1; i < cmpTree[min].length; i++) {
                    delete cmpTree[cmpTree[min][i]];
                }
                min = cmpTree[min][0];
                // If the order is not fully determined, cmpTree could be empty
                // yet we may still have elements left in arr.
                if (min === undefined && arr.length > 0) {
                    min = arr[arr.length - 1];
                    cmpTree[min] = [];
                }
                break;
            }

            let x = arr[xIdx];
            if (x in cmpTree) continue;
            let c = cmp(x, min);
            if (c === '>') {
                cmpTree[min].push(x);
                cmpTree[x] = [];
            }
            if (c === '<') {
                cmpTree[x] = [min];
                min  = x;
                xIdx = -1;
            }
        }
    }

    return sorted;
}