6

When you sort the output of a Stack Exchange Data Explorer query by a column that contains duplicate values, any rows sharing the same value in the column will end up ordered semi-randomly relative to each other. Repeatedly sorting the data by the same column will cause the relative order of the rows to change. Here's a quick test to demonstrate this:

Animated screenshot of unstable data sorting

Note how the numbers are initially sorted in ascending numerical order, but sorting them by their parity ("even" or "odd") jumbles the relative order of the numbers having the same parity.

It would be much more useful if the sorting operation was stable, so that sorting data by a column would not change the relative order of rows that have the same value in that column.

The problem is that the client-side sorting implementation used by SEDE is based on SlickGrid, which simply uses JavaScript's array sort() method, which is not guaranteed to be stable. (Note that some browsers may use a stable sorting algorithm, so this behavior can be browser dependent. I used Chromium 64 for the test above. See also SlickGrid issue #320.)

To fix this, either the sorting code should be rewritten to use a naturally stable sorting algorithm (such as merge sort), or the sort should be stabilized by making the comparison function break ties based on the current order of the rows.


Ps. See also Stable sort in SlickGrid, a blog post from 2013 that I found on Google, discussing this very issue and how to solve it.

2
  • I personally never use the client-side sort. If I need a stable sort I use an order by clause in the SQL statement
    – rene
    Mar 5, 2018 at 20:42
  • @rene: That's one work-around, but editing the query (even trivially) and rerunning it takes quite a bit more time and effort than just clicking a column header. For queries like the dupes of deleted questions list, I quite like the ability to quickly sort the output by different criteria. It would be even more convenient if the sorting was stable. Mar 5, 2018 at 20:54

1 Answer 1

3

One practical way to solve this problem would be to simply replace the native JS sort() method with a stable reimplementation. Here's one I just wrote for SOUP:

// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort:
// "If omitted, the array is sorted according to each character's Unicode code point value, according to the string conversion of each element."
// XXX: The merge sort implementation below always provides the arguments to compare() in their original order, so we can treat a == b and a < b the same way!
// XXX: ("" + x) is almost 10 times faster than String(x) on Firefox 58, especially when the input is already a string!
function defaultCompare (a, b) {
    return ("" + a) > ("" + b);
}

// merge the arrays left and right into output, based on the given comparison function
function merge (left, right, output, compare) {
    if ( ! compare ) compare = defaultCompare;
    var i = 0, j = 0, k = 0;
    while ( i < left.length && j < right.length ) {
        var cmp = compare( left[i], right[j] );
        output[k++] = ( cmp <= 0 ? left[i++] : right[j++] );
    }
    while ( i < left.length ) output[k++] = left[i++];
    while ( j < right.length ) output[k++] = right[j++];
}

// sort an array in-place using insertion sort, based on the given comparison function
function insort (array, compare) {
    if ( ! compare ) compare = defaultCompare;
    for ( var i = 1; i < array.length; i++ ) {
        var j = i, x = array[i];
        while ( j > 0 && compare( array[j-1], x ) > 0 ) {
            array[j] = array[j-1]; j--;
        }
        array[j] = x;
    }
}

// custom stable .sort() method
Array.prototype.sort = function (compare) {
    if ( this.length < 16) {
        // use an insertion sort for short arrays (TODO: optimize threshold)
        insort(this, compare);
    } else {
        // recursively sort and merge subarrays
        var midpoint = this.length >> 1;
        var left = this.slice(0, midpoint).sort(compare);
        var right = this.slice(midpoint).sort(compare);
        merge(left, right, this, compare);
    }
    return this;
};

I've tested this on SEDE with Chromium 64, and it seems to work fine.

I have not yet benchmarked this implementation to compare its efficiency with the native Chromium sort() implementation, but it should be reasonably efficient for a pure-JS merge sort, and in any case more than fast enough for SEDE.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .