Are there plans to implement a guaranteed-stable sorting method?

[cspotcode]

I have a case where I'm using _.sortBy to order an array of objects by an optional "order" property that is almost always undefined.

_.sortBy(objects, function(v) {return v.order || Number.POSITIVE_INFINITY});

These objects are then rendered in a list visible to the user, so using an unstable sort algorithm (like in V8) confuses the user by causing items to jump up and down the list seemingly for no reason.

I've solved my problem with my own stable sort function based on a modified implementation of _.sortBy. However, I'm wondering if you plan to add built-in support for "forcing" the sort to be stable, perhaps with an optional argument?

_.sortBy(collection, callback, thisArg, forceStable)

Thanks!

[jdalton]

More info on V8's unstable sort here:
http://code.google.com/p/v8/issues/detail?id=90

[jdalton]

I'll do some research and see what the cost would be, that will help me figure out how to handle it. Worst case there can at least be a build option for it.

[cspotcode]

For what it's worth, here's how I implemented stable sorting:

In the beginning of _.sortBy, when it's mapping the list of values onto criteria&value objects, I also add the index as a property:

result[index] = {
    criteria: callback(value, index, collection),
    value: value,
    index: index
}

And I created a modified compareAscending that looks at index when the criteria values are equal.

function compareAscending(a, b) {
    var ai = a.index;
    var bi = b.index;
    a = a.criteria;
    b = b.criteria;

    if (a === undefined) {
      return 1;
    }
    if (b === undefined) {
      return -1;
    }
    return a < b ? -1 : a > b ? 1 : ai < bi ? -1 : 1;
  }

[jdalton]

And I created a modified compareAscending

Awesome! I will patch this. It might slip into the 0.5.0 release.

[sethrosenblum]

Wait, what if both criteria are undefined?

[jdalton]

@ricklerre Good call. I'll patch that up.

[jdalton]

patched here.

[lock]

This thread has been automatically locked since there has not been any recent activity after it was closed. Please open a new issue for related bugs.