array.sort() compare function weirdness in ExtendScript

[Jan Pietkiewicz]

I'm posting this in InDesign Scripting forum, since I encountered the problem while working on a script for InDesign CC 2015, but it seems to concern the whole of ExtendScript.

In my script, I'm using the array.sort() method with a custom compare function in order to sort an array of objects with respect to one of their properties. I will present a generalized version of the relevant part so that it's easier to analyze and replicate.

var myArray = [{
    name: "A",
    size: 20
}, {
    name: "B",
    size: 10
}, {
    name: "C",
    size: 30
}, {
    name: "D",
    size: 30
}];

myArray.sort(
    function(a, b) {
        if (a.size > b.size) {
            return 1;
        }
        if (b.size > a.size) {
            return -1;
        }
        return 0;
    });


var names = [];
for (var i = 0; i <= myArray.length - 1; i++) {
    names.push(myArray.name)
};
names;

The expected result is "B,A,C,D". B should go before A, since it's size is smaller than A's, while the order of C and D should remain unchanged, since their size is equal.

However, the result provided by ExtendScript is "B,A,D,C". For some reason, C and D become reversed.

I believe that the source of this behavior lies with ExtendScript's incorrect processing of the return 0 part.

In order to confirm that, I replaced the sorting funcion with

myArray.sort(
    function(a, b) {
        return 0;
    });

which, according to my understanding of how compare functions are supposed to work, should return the whole array unchanged (no matter the input). But in this case ExtendScript processes it as "B,C,D,A".

I would be very grateful if anyone could confirm whether it is indeed a bug (or at least a lackluster implementation of the ECMAScript standard). Or is everything working as it should and the mistake is on my part?

Any hints as to the workaround for this issue would also be very helpful. Thanks!

[TᴀW]

Interesting. It does seem to be an Extendscript bug. Your code works as expected in Chrome, for instance.

Ariel

[Vamitul]

Yes, it looks like a weirdness in ExtendScript. Using myArray.reverse().sort(blah blah) should do the trick.

[Jan Pietkiewicz]

Thanks for your answer.

The addition of .reverse() does indeed correct the behavior of the sorting in the above particular case, but unfortunately it is not a universal solution to the problem: it only makes sense if the original order of the array items before the sorting doesn't matter.

Let's say that the array I'd like to sort looks like this:

var myArray = [{
name: "A",
size: 10
}, {
name: "B",
size: 20
}, {
name: "C",
size: 10
}, {
name: "D",
size: 20
}, {
name: "E",
size: 10
}];

The result of the sorting by size should move the items B and D to the end (in that order), while keeping the relations between all the other objects intact: A, C, E, B, D. Reversing the array before applying the .sort() method obviously doesn't allow for that.

Any other ideas?

[TᴀW]

Jan Pietkiewicz wrote:

Any other ideas?

Write your own sort function? Override the default Array.sort method:

Array.prototype.sort = function(){
  alert("First element: " + this[0] + ". Second element: " + this[1]);
}
a = ["apple", "orange", "pear"];
a.sort();

Obviously, change the inside of the function to do a proper sort.

You would be losing the speed of native C code, so if you're doing a lot of this, it may not be ideal...

Ariel

[Jan Pietkiewicz · Accepted solution]

Thanks for this suggestion!

Your answer made me read up on different sorting algorithms and their implementation in different JavaScript engines. Apparently, ExtendScript uses what is known as an unstable sorting algorithm, which is precisely the cause for unwanted behavior with equal values in the sorting condition.

Implementing a different, stable algorithm (such as merge sort) within your script is surely an option, but it seemed like overkill for my purposes.

Fortunately, I was able to find another solution.

First, add a "position" property to each element of the array, based on its current position. For example:

for (i = 0; i < myArray.length; i++) myArray.position = i;

Then, simply change the last condition of the sorting function so that it compares each element's position:

myArray.sort(function(a, b) {
    if (a.size > b.size) {
        return 1;
    }
    if (b.size > a.size) {
        return -1;
    }
    if (a.size == b.size) {
        return a.position - b.position;
    }
});

I hope this will be of use to those who may encounter the problem in the future.

[Harbs.]

Interesting discussion. Can anyone think of a reason not to do this?

myArray.sort( 
    function(a, b) { 
        if (a.size > b.size) { 
            return 1; 
        } 
        if (b.size > a.size) { 
            return -1; 
        } 
    return 1;
    }); 

[Marc Autret]

I don't think that would be a good idea to override Array.prototype.sort.

The native method is fast, and even dramatically fast when called with no custom compare function. Some tests and experiments are reported here:

— http://www.indiscripts.com/post/2015/05/reconsidering-array-sort-in-extendscript-javascript-1

— http://www.indiscripts.com/post/2015/05/reconsidering-array-sort-in-extendscript-javascript-2

An interesting approach is to create temporary UTF16 keys to get both quick and stable sort for an array of objects, provided that the key property offers unsigned integers in the range [0,0xFFFF].

Here is a generic function:

function stableSortByProp(/*&obj[]*/a,/*str*/prop,  i,t)
// -------------------------------------
// This func is intended to sort fast & stable an array of objects
// along a property `prop` that takes UINT values in [0..0xFFFF].
// (Performance gain should be sensible for array.length≈10^3.)
{
    const CHR = String.fromCharCode;
    for( i=a.length ; i-- ; a['_'+i]=t=a, a=CHR(t[prop])+CHR(i) );
    a.sort();
    for( i=a.length ; i-- ; a=a[t='_'+a.charCodeAt(1)], delete a );
}

// Test
// ---
var myArray = [{  
    name: "A",  
    size: 20  
}, {  
    name: "B",  
    size: 10  
}, {  
    name: "C",  
    size: 30  
}, {  
    name: "D",  
    size: 30  
}];  


stableSortByProp(myArray,'size');

var names = [];  
for (var i = 0; i <= myArray.length - 1; i++) {  
    names.push(myArray.name)  
};  

alert( names ); // => B,A,C,D

@+

Marc

[Harbs.]

Nice solution Marc, but your functions are really friggen hard to read...

[Marc Autret]

According to ECMA 262/3 Array.prototype.sort(comparefn) has not to perform a stable sort:

ECMA 262/3 (page 102)

The sort is not necessarily stable (that is, elements that compare equal do not necessarily remain in their original order). If comparefn is not undefined, it should be a function that accepts two arguments x and y and returns a negative value if x < y, zero if x = y, or a positive value if x > y.

hence IMHO that's not a bug.

@+

Marc