Sort an array using a partial order, ie, using a cmp() function which may return "not sure" as an answer.

partial_order.js

// The inputArr is an array of any kind of values.
// The inputCmp() function accepts two values, x and y; with the return
// value indicating the relationship as such:
//
//   If:         then cmp(x, y) returns:
//   x < y       '<'
//   x > y       '>'
//   x = y       '='
//   x ? y       null
//
// This breaks precendent with the cmp interface in other settings, such
// as the compareFn() used by Array.sort(), but I find this interface to
// be much more intuitive.
//
// The inputCmp() function is internally memoized since it may be expensive,
// and otherwise we would call it redundantly.
function sortWithPartialOrder(inputArr, inputCmp) {

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

    let objectIdCounter = 0;
    const objectIdMap = new Map();
    function objectId(obj) {
        if (!objectIdMap.has(obj)) {
            objectIdMap.set(obj, ++objectIdCounter);
        }
        return objectIdMap.get(obj);
    }

    const cache = new Map();
    function cmp(a, b) {
        let [aId, bId] = [objectId(a), objectId(b)];
        let key = aId + ':' + bId;
        if (cache.has(key)) return cache.get(key);

        let result = inputCmp(a, b);
        cache.set(key, result);

        let newKey = bId + ':' + aId;
        let newResult = result;
        if (result === '<') newResult = '>';
        if (result === '>') newResult = '<';
        cache.set(newKey, newResult);

        return result;
    }

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

    let arr    = [...inputArr];  // Make a copy that we can modify.
    let sorted = [];

    while (arr.length > 0) {

        // Ensure the first element in `arr` is minimal.
        while (true) {
            let didChange = false;
            for (let i in arr) {
                if (cmp(arr[0], arr[i]) == '>') {
                    didChange = true;
                    arr.unshift(...arr.splice(i, 1));
                }
            }
            if (!didChange) break;
        }

        // Append that to `sorted`.
        sorted.push(...arr.splice(0, 1));
    }

    return sorted;
}

I created this gist as a first pass, and then realized a couple things:

• The problem I'm solving is not strictly about what a mathematician would call a "partial order" because I'm not assuming that the user-given comparison function is transitively closed. I am assuming it is internally consistent, but, for example, it's ok with me if inputCmp() reports that a < b and b < c but then says a ? c. In a sense, this problem is harder to solve because I'm given less information and have to use less structured clues.
• The code can be more efficient. This code is a little like bubble sort. In particular, this code does not try so hard to reuse previously known comparisons.

With those two things in mind, I created an updated version of this algorithm here.