What is the default sort for 2D arrays?

Question

when using Array.sort()

I would assume it takes the first index but I wanted to verify.

MDN reference did not say anything:

This SO Post is not relevant.

For this method: ( sorting off the first index will work fine ).

$P.aZindex = function () {
    var arr_2d = {},
        elements = document.body.getElementsByTagName("*"),
        element,
        length,
        z_index;

    // loop through elements and pull information from them
    $A.eachIndex(elements, function(val, index){
        z_index = win.getComputedStyle(val).getPropertyValue("z-index");

        // ignore elements with the auto value
        if (z_index !== "auto") {
            arr_2d[i] = [val.id, val.tagName, val.className, z_index];
        }
    });

    // sort the array
    arr_2d.sort();
    return arr_2d;
};

apsillers · Accepted Answer · 2013-11-06T21:40:36.830

Let's examine the EMCAScript specification for the array sort method. The sort algorithm iteratively compares pairs of elements from the array; those comparisons yield either -1, 1, or 0 (for less than, greater than, or equal to, respectively), and the result of each comparison is used to build a sorted array.

In particular, we are concerned with the "default" comparison case of sort, in which no comparison function is specified. When comparing some pair of x and y:

Let xString be ToString(x).

Let yString be ToString(y).

If xString < yString, return −1.

If xString > yString, return 1.

Return +0.

ECMAScript's ToString, when applied to objects, calls the object's toString method.

To clarify what is meant by x > y and x < y, we can examine ECMAScript's Abstract Relational Comparison Algorithm, which specifies the behavior of the > and < operators. In the event that the operands px and py are both strings:

Let k be the smallest nonnegative integer such that the character at position k within px is different from the character at position k within py...

Let m be the integer that is the code unit value for the character at position k within px.

Let n be the integer that is the code unit value for the character at position k within py.

If m < n, return true. Otherwise, return false.

This is a simple string comparison, based on a comparison of Unicode code unit values of the character at the first differing position within the strings.

As you can see, the sort algorithm stringifies each object element (using the element's toString method) that it contains and then compares those strings to determine ordering. I understand that this seems strange to you: if you have nothing but array elements in your sorting array, why not use the elements of those subarrays to determine ordering? This is simply because the EMCAScript specification chose to keep default element comparison of a potentially heterogeneous array extremely general, since any type of element can be rendered as a string.

However, if array-descent behavior is what you want, it's possible to implement:

var compare_items = function(a,b) {
    var result;
    if(a instanceof Array && b instanceof Array) {
        // iteratively compare items from each array
        for(var i=0; i<Math.min(a.length,b.length); ++i) {
            result = compare_items(a[i], b[i]);
            if(result != 0) { return result; }
        }

        // if both arrays are equal so far, length is the determining factor
        return a.length - b.length;
    }

    // if the items are both numbers, report their numeric relation
    if(typeof a == "number" && typeof b == "number") {
        return a - b;
    }

    // otherwise, fall back to strings
    if(a.toString() == b.toString()) { return 0; }
    return a.toString() > b.toString() ? 1 : -1;
}

Then, use this comparator function like arr_2d.sort(compare_items);.

This allows you to sort arbitrarily deep N-dimensional arrays. First we compare a[0]...[0][0] against b[0]...[0][0] then a[0]...[0][1] to b[0]...[0][1]; then, if the [0]...[0][*] subarray proves equal, we move up to a[0]...[1][0], etc. Comparing arrays of differing dimension may produce unusual results, because a non-array may be compared to an array, which compares the stringified forms of each operand.

Note that this function has strange results if you have a heterogeneous array: [1, 2, 3, [1,2], [2,3]] sorts to [1, [1,2], 2, [2,3], 3]. The arrays and non-array are relatively sorted correctly, but the arrays are scattered in with the non-arrays in a non-intuitive way.

score 1 · Answer 2 · answered Nov 06 '13 at 14:50

1

From the documentation you link to:

the array is sorted lexicographically (in dictionary order) according to the string conversion of each element

This doesn't change just because those elements are also arrays.

answered Nov 06 '13 at 14:50

Quentin

914,110
126
1,211
1,335

What is the default sort for 2D arrays?

2 Answers2