Skip to main content
Participant
April 11, 2016
Answered

array.sort() compare function weirdness in ExtendScript

  • April 11, 2016
  • 3 replies
  • 4202 views

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!

This topic has been closed for replies.
Correct answer Jan Pietkiewicz

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


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.

3 replies

Marc Autret
Legend
April 12, 2016

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

Vamitul
Legend
April 11, 2016

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

Participant
April 11, 2016

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
Legend
April 11, 2016

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

Visit www.id-extras.com for powerful InDesign scripts that save hours of work — automation, batch tools, and workflow boosters for serious designers.
TᴀW
Legend
April 11, 2016

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

Ariel

Visit www.id-extras.com for powerful InDesign scripts that save hours of work — automation, batch tools, and workflow boosters for serious designers.