Can you sort an array of opaque object instances in JavaScript? NOT by a property

Question

THIS IS NOT A QUESTION OF SORTING BY A PROPERTY!!

Assume I have an array of object instances. Many instances are in the array more than once.

var array = [
  opaqueObjectA,
  opaqueObjectB,
  opaqueObjectA,
  opaqueObjectC,
  opaqueObjectB,
  opaqueObjectC,
  opaqueObjectA,
];

I don't care about the order, I care that the objects that are the same instance end up next to each other. In other words after sorting, one possible result would be

var array = [
  opaqueObjectB,
  opaqueObjectB,
  opaqueObjectC,
  opaqueObjectC,
  opaqueObjectA,
  opaqueObjectA,
  opaqueObjectA,
];

I don't care if the A's or the B's or the C's come first, I only care that objects of the same instance are next to each other after sorting.

So the questions are

1. is JavaScript sort guaranteed to handle this case?

2. If not how can I do it? The sort function requires me to return -1 if a < b, 1 of a > b and 0 if a === b but given the objects are opaque, and since I don't have access to pointer values or something else, I have nothing to compare them with to get a less than or greater than result, only an equal result.

I can go add some sortId to each opaque object but that seems kind of bad to add properties to objects, I'd have no idea if I'm cobbering a property. I could make another set of objects, each with an id and a reference to one instance, sort those, then collect their instances into a new array. That also seems rather lame to have to go build an entire array of objects to sort.

Actually I'd also like to be able to sort by multiple instances which is a property but still not comparable. Example:

var array = [
  { thing: opaqueThingA, stuff: opaqueStuffG, },
  { thing: opaqueThingA, stuff: opaqueStuffH, },
  { thing: opaqueThingB, stuff: opaqueStuffG, },
  { thing: opaqueThingC, stuff: opaqueStuffG, },
  { thing: opaqueThingB, stuff: opaqueStuffH, },
  { thing: opaqueThingA, stuff: opaqueStuffG, },
  { thing: opaqueThingA, stuff: opaqueStuffH, },
  { thing: opaqueThingC, stuff: opaqueStuffG, },
];

I'd like to be able to sort them first by thing, then by stuff. So one possible result would be

var array = [
  { thing: opaqueThingB, stuff: opaqueStuffG, },
  { thing: opaqueThingB, stuff: opaqueStuffH, },
  { thing: opaqueThingA, stuff: opaqueStuffG, },  // Note the G' s 
  { thing: opaqueThingA, stuff: opaqueStuffG, },  // Are next to
  { thing: opaqueThingA, stuff: opaqueStuffH, },  // each other
  { thing: opaqueThingA, stuff: opaqueStuffH, },
  { thing: opaqueThingC, stuff: opaqueStuffG, },
  { thing: opaqueThingC, stuff: opaqueStuffG, },
];

This would be trivial in C/C++ because I could just compare the addresses of the instances. Is there a way to do this in JavaScript without dirtying the objects with hacked on properties and without making temporary arrays just for sorting?

Answer 1

You cannot do it using Array.prototype.sort because the arguments sent to the comparator function are only objects and you need to keep track of the objects yourself somewhere.

var objectA = {name: 'objectA'}, objectB = {name: 'objectB'}, objectC = {name: 'objectC'};
var original = [objectA, objectB, objectA, objectC, objectB, objectC, objectA];

var instanceSort = function (original) {
        var seen = [], comparator = function (a, b) {
                if (seen.indexOf(a) === -1) seen.push(a);
                if (seen.indexOf(b) === -1) seen.push(b);
                return seen.indexOf(a) - seen.indexOf(b);
        }
        return original.sort(comparator);
}

var sorted = instanceSort(original);
console.log(sorted);

If you need to call this function multiple times, you could add it to Array.prototype like so, instead of polluting the scope:

Array.prototype.instanceSort = function (original) { ... }

and then call it on your array like so: var sorted = original.instanceSort()

---

@steady rain complained that this is inefficient, so here's an improved version:

var instanceSort = function (original) {
    var i, o, comparator, sorted;

    for (i = original.length - 1; i >= 0; i--) {
        o = original[i];
        if (!o.hasOwnProperty('__instanceSortIndex')) o.__instanceSortIndex = i;
    }

    comparator = function (a, b) {
        return a.__instanceSortIndex - b.__instanceSortIndex;
    }

    sorted = original.sort(comparator);

    for (i = original.length - 1; i >= 0; i--) {
        delete original[i].__instanceSortIndex;
    }

    return sorted;
}

this assumes you'll never ever need to use a property called __instanceSortIndex on any object that might ever end up being sorted by this function. It's a bit dirty in theory, but it's safe to use in practice.

---

Here's another one, but it will only work if you're targeting modern browsers which support WeakMap and you like the idea of sending the function as argument to .sort():

var objectA = {name: 'objectA'}, objectB = {name: 'objectB'}, objectC = {name: 'objectC'};
var original = [objectA, objectB, objectA, objectC, objectB, objectC, objectA];

var instanceSort = function (a, b) {
        if (!instanceSort.history) {
                instanceSort.history = new WeakMap();
                instanceSort.uid = 0;
        }

        var h = instanceSort.history, aIndex, bIndex;
        if (h.has(a)) aIndex = h.get(a);
        else h.set(a, aIndex = ++instanceSort.uid);
        if (h.has(b)) bIndex = h.get(b);
        else h.set(b, bIndex = ++instanceSort.uid);

        return aIndex - bIndex;
}

var sorted = original.sort(instanceSort);

A WeakMap can hold existing object as keys but it will not add to the object reference count, so basically you can use it to store hidden properties without worrying that you're also holding references and creating memory leaks. In this case I am using a WeakMap inside the instanceSort comparator function to assign a unique integer identifier to each object it receives as argument and use the difference between identifiers as the "difference" between objects.

The downside is that you cannot use it for browsers older than IE11, Firefox 31 ESR, Safari 7.1, iOS 7, Konqueror (all versions) and Opera (all versions). See the link above for detailed information regarding browsers which support WeakMap.

Answer 2

My interpretation of your question is that you wanna sort by type so here is what I came up with :

function Test() {} // Dummy object
var test = [a = 1, b = 2, c = 3, a, "titi", b, c, new Test(), a, b, c, new Test(), "toto"]; // Test Array

function sortByType(cpy) {
    var arr = cpy.slice();
    var arrs = [];
    var ret = [];
    for (var i = 0; i < arr.length; i++) {
        for (var j = 0; j < arrs.length; j++) {
            if (arrs[j][0].__proto__ === arr[i].__proto__) {
                arrs[j].push(arr[i]);
                arr[i] = null;
                break;
            }
        }
        if (arr[i] !== null) {
            arrs.push([arr[i]]);
            arr[i] = null;
        }
    }
    ret = Array.prototype.concat.apply([], arrs);
    return (ret);
}
test = sortByType(test); // [1, 2, 3, 1, 2, 3, 1, 2, 3, "titi", "toto", Test, Test]

I basically compare x.__proto__ to check whether object are from the same parent or not.

Edit : Fixed a typo thanks to @Travis J Edit : Changed clone method

Answer 3

It seems to me you can use the native Array.prototype.sort() for primary/secondary grouping since the objects in the array are the same object used multiple times. The approach I've come up with does not modify the objects, but does use a temporary array and create a new, grouped array based on both the primary and secondary "sort" items. I'm not sure how true sorting can be accomplished when the object is opaque since you have to have some criteria by which you can sort by.

//object setup
//inner objects, note that "name" is a convention only used to identify sort order (secondary grouping)
var innerObjA = { "name": "a" };
var innerObjB = { "name": "b" };
var innerObj1 = { "name": "1" };
var innerObj2 = { "name": "2" };
var innerObj3 = { "name": "3" };
//parenting objects (primary grouping)
var obj1 = { "first": innerObjA, "second": innerObj1 };
var obj2 = { "first": innerObjA, "second": innerObj2 };
var obj3 = { "first": innerObjA, "second": innerObj1 };
var obj3 = { "first": innerObjB, "second": innerObj1 };
var obj4 = { "first": innerObjB, "second": innerObj1 };
var obj5 = { "first": innerObjB, "second": innerObj2 };
var obj6 = { "first": innerObjB, "second": innerObj3 };

//out of order array
var original = [obj6, obj2, obj4, obj1, obj5, obj3];

//helper to show the order of these objects
function showOrder(myArray){
  myArray.forEach(function(index) { console.log(index.first.name, index.second.name); });
  console.log('-----------');
}

//helper to handle the native sort
function doNativeSort(myArray, sortBy) {
  myArray.sort(function(a, b) { 
    return a[sortBy]===b[sortBy]?0:1;
  });
  return myArray; //returns so we can use in-line
}

showOrder(original);

//primary sort is done by the property "first" within the objects  
// in our array, since the OP states that many instances of an  
// object are in the array more than once, the native JS sort will  
// work to GROUP items which is what we do here.
doNativeSort(original, "first");

showOrder(original);

//secondary sort is more challenging and requires temp arrays 
// to group the like items so that we can again use the native  
// sort, we'll use the reduce method to compare the array that  
// already has the first grouping/sorting applied to it.
function myReduce(original) {
  var newArr = [], subGroup = []; //new stuff
  
  original.reduce(function(previousValue, currentValue) {
    if (previousValue.first === currentValue.first) {
      subGroup.push(currentValue);
    } else {
      if (subGroup.length > 0) {
        //concat the sorted sub-group onto the new array
        newArr = newArr.concat(doNativeSort(subGroup, "second"));
      }
      //starting the next subgroup
      subGroup = [currentValue];
    }
    //becomes the previous value in the next invocation
    return currentValue;
  }, original[0]);
  
  //sort the final subGroup and add to the new array
  newArr = newArr.concat(doNativeSort(subGroup, "second"));
  
  return newArr;
}

var groupedArray = myReduce(original);

showOrder(groupedArray);

http://jsbin.com/yeboyosome/4/edit?js,console

I'd watch performance in general for this problem. This approach could be inefficient for large arrays since we're defaulting to 1 if the objects are not equal in the native Array.prototype.sort() method (potentially forcing more invocations of the compareFunction).