Sort Array B after Array A, such that references and equal Primitives, maintain the exact Position

Question

Update 2

I added a weight lookup to the sort function, which increased the performance by about 100% as well as the stability, as the previous sort function didn't consider all types, and as 1 == "1" the result depends on the initial order of the Array, as @Esailija points out.

The intent of the question is to improve this Answer of mine, I liked the question and since it got accepted and I felt like there is some performance to squeeze out of the sort function. I asked this question here since I hadn't many clues left where to start.
_{Maybe this makes things clearer as well}

Update

I rephrased the complete question, as many people stated I was not specific enough, I did my best to specify what I mean. Also, I rewrote the sort function to better express the intent of the question.

• Let arrayPrev be an Array (A) ,where A consists of 0 to n Elements' (E)

  • Let an Element either be
    • of a Primitive type
      • boolean, string, number, undefined, null
    • a Reference to an Object O, where O.type = [object Object] and O can consist of
      • 0 to n Properties P, where P is defined like Element plus
        • an circular Reference to any P in O
      • Where any O can be contained 1 to n times. In the sense of GetReferencedName(E1) === GetReferencedName(E2)...
    • a Reference to an O, where O.type = [object Array] and O is defined like A
    • a circular Reference to any E in A
• Let arrayCurr be an Array of the same length as arrayPrev

Illustrated in the following example

var x = {
    a:"A Property",
    x:"24th Property",
    obj: {
        a: "A Property"
    },
    prim : 1,
}
x.obj.circ = x;

var y = {
    a:"A Property",
    x:"24th Property",
    obj: {
        a: "A Property"
    },
    prim : 1,
}
y.obj.circ = y;
var z = {};

var a = [x,x,x,null,undefined,1,y,"2",x,z]
var b = [z,x,x,y,undefined,1,null,"2",x,x]    
console.log (sort(a),sort(b,a))

The Question is, how can I efficiently sort an Array B, such that any Reference to an Object or value of a Primitive, shares the exact same Position as in a Previously, by the same compareFunction, sorted, Array A.

Like the above example

Where the resulting array shall fall under the rules.

• Let arrayPrev contain the Elements' of a and arrayCurr contain the Elements' of b
  1. Let arrayPrev be sorted by a CompareFunction C.
  2. Let arrayCurr be sorted by the same C.
     • Let the result of sorting arrayCur be such, that when accessing an E in arrayCur at Position n, let n e.g be 5
       • if type of E is Object GetReferencedName(arrayCurr[n]) === GetReferencedName(arrayPrev[n])
       • if type of E is Primitive GetValue(arrayCurr[n]) === GetValue(arrayPrev[n])
       • i.e b[n] === a[n] e.g b[5] === a[5]
     • Meaning all Elements should be grouped by type, and in this sorted by value.
     • Where any call to a Function F in C shall be at least implemented before ES5, such that compatibility is given without the need of any shim.

My current approach is to Mark the Objects in arrayPrev to sort them accordingly in arrayCurr and later delete the Marker again. But that seems rather not that efficient. Heres the current sort function used.

function sort3 (curr,prev) {
         var weight = {
            "[object Undefined]":6,         
            "[object Object]":5,
            "[object Null]":4,
            "[object String]":3,
            "[object Number]":2,
            "[object Boolean]":1
        }
        if (prev) { //mark the objects
            for (var i = prev.length,j,t;i>0;i--) {
                t = typeof (j = prev[i]);
                if (j != null && t === "object") {
                     j._pos = i;   
                } else if (t !== "object" && t != "undefined" ) break;
            }
        }

        curr.sort (sorter);

        if (prev) {
            for (var k = prev.length,l,t;k>0;k--) {
                t = typeof (l = prev[k]);
                if (t === "object" && l != null) {
                    delete l._pos;
                } else if (t !== "object" && t != "undefined" ) break;
            }
        }
        return curr;

        function sorter (a,b) {

             var tStr = Object.prototype.toString
             var types = [tStr.call(a),tStr.call(b)]
             var ret = [0,0];
             if (types[0] === types[1] && types[0] === "[object Object]") {
                 if (prev) return a._pos - b._pos
                 else {
                     return a === b ? 0 : 1;
                 }
             } else if (types [0] !== types [1]){
                     return weight[types[0]] - weight[types[1]]
             }



            return a>b?1:a<b?-1:0;
        }

    }

Heres a Fiddle as well as a JSPerf _{(feel free to add your snippet)
And the old Fiddle}

Answer 1

from the description, it appears you can simply use a sort function:

function sortOb(a,b){a=JSON.stringify(a);b=JSON.stringify(b); return a===b?0:(a>b?1:-1);}
var x = {a:1};
var y = {a:2};

var a = [1,x,2,3,y,4,x]
var b = [1,y,3,4,x,x,2]

a.sort(sortOb);
b.sort(sortOb);
console.log (a,b);

Answer 2

If you know the arrays contain the same elements (with the same number of repetitions, possibly in a different order), then you can just copy the old array into the new one, like so:

function strangeSort(curr, prev) {
    curr.length = 0;             // delete the contents of curr
    curr.push.apply(curr, prev); // append the contents of prev to curr
}

If you don't know the arrays contain the same elements, it doesn't make sense to do what you're asking.

Judging by the thing you linked, it's likely that you're trying to determine whether the arrays contain the same elements. In that case, the question you're asking isn't the question you mean to ask, and a sort-based approach may not be what you want at all. Instead, I recommend a count-based algorithm.

1. Compare the lengths of the arrays. If they're different, the arrays do not contain the same elements; return false. If the lengths are equal, continue.
2. Iterate through the first array and associate each element with a count of how many times you've seen it. Now that ES6 Maps exist, a Map is probably the best way to track the counts. If you don't use a Map, it may be necessary or convenient to maintain counts for items of different data types differently. (If you maintain counts for objects by giving them a new property, delete the new properties before you return.)
3. Iterate through the second array. For each element,
   1. If no count is recorded for the element, return false.
   2. If the count for the element is positive, decrease it by 1.
   3. If the count for the element is 0, the element appears more times in the second array than in the first. Return false.
4. Return true.

If step 4 is reached, every item appears at least as many times in the first array as it does in the second. Otherwise, it would have been detected in step 3.1 or 3.3. If any item appeared more times in the first array than in the second, the first array would be bigger, and the algorithm would have returned in step 1. Thus, the arrays must contain the same elements with the same number of repetitions.

Answer 3

Your function always returns a copy of sort.el, but you can have that easier:

var sort = (function () {
    var tmp;

    function sorter(a, b) {
        var types = [typeof a, typeof b];
        if (types[0] === "object" && types[1] === "object") {
            return tmp.indexOf(a) - tmp.indexOf(b); // sort by position in original
        }
        if (types[0] == "object") {
            return 1;
        }
        if (types[1] == "object") {
            return -1;
        }
        return a > b ? 1 : a < b ? -1 : 0;
    }


    return function (el) {
        if (tmp) {
            for (var i = 0; i < el.length; i++) {
                el[i] = tmp[i]; // edit el in-place, same order as tmp
            }
            return el;
        }
        tmp = [].slice.call(el); // copy original
        return tmp = el.sort(sorter); // cache result
    };

})();

Note that I replaced sort.el by tmp and a closure. Fiddle: http://jsfiddle.net/VLSKK/

---

Edit: This (as well as your original solution)

• only works when the arrays contain the same elements.
• maintains the order of different objects in a

but

• does not mess up when called more than twice

Answer 4

Try this

function ComplexSort (a, b)
{
     if(typeof a == "object") { 
        a = a.a; 
    } 
    if(typeof b == "object") { 
       b = b.a;
    } 
    return a-b;
}

var x = {a:1};
var y = {a:2};

var a = [1,x,2,3,y,4,x]
var b = [1,y,3,4,x,x,2]

a.sort(ComplexSort);
b.sort(ComplexSort);
console.log ("Consistent", a,b);