Results 1 to 2 of 2

Thread: Ext.Array.sort not truly stable in Chrome

    You found a bug! We've classified it as EXTJS-5801 . We encourage you to continue the discussion and to find an acceptable workaround while we work on a permanent fix.
  1. #1
    Sencha Premium Member
    Join Date
    Sep 2011
    Posts
    51

    Default Ext.Array.sort not truly stable in Chrome

    I originally posted this under the thread "Tree Node Ordering", but I'm not sure that thread's still active (and the bug really isn't limited to tree node order) so I'm re-posting here...

    The problem is that Ext's logic for detecting the presence of a stable sort won't work for Chrome. Chrome actually uses 2 different sort algorithms: a stable algorithm for small arrays, and a non-stable (quicksort) algorithm for large ones. According to my tests, a "small" array has <= 10 elements. Ext's test uses only 5 elements, and hence, detects Chrome's sort algorithm as stable; most grids, unfortunately, will have more than 5 nodes, resulting in a broken (unstable) sort...

    Note that there was actually a bug opened against the V8 JS engine for this in 2008, but the bug status is "WorkingAsIntended". Here's the thread:

    http://code.google.com/p/v8/issues/detail?id=90


    I created the following workaround for my own usage, but I would suggest that the number of elements used in the Ext test needs to be increased...


    Code:
            // Caveat: This method returns a stable-sorted copy of the original array; unlike builtin and Ext sort,
            // it does NOT modify the original!!!
            Ext.Array.trulyStableSortCopy = function(a, fn) {
                var i = 0,
                    fnw = function(a, b) {
                        var res = fn(a.v, b.v);
                        return res !== 0 ? res : a.i - b.i;
                    };
                return Ext.Array.map(
                    Ext.Array.sort(
                        Ext.Array.map(a, function(v) {
                            return { i: i++, v: v };
                        }), fnw),
                    function(v) { return v.v; });
            };
    Last edited by stahlman; 2 Apr 2012 at 10:13 AM. Reason: Noticed link was corrupted by following text on same line.

  2. #2
    Sencha Premium User mitchellsimoens's Avatar
    Join Date
    Mar 2007
    Location
    Gainesville, FL
    Posts
    40,379

    Default

    Thanks for the report.
    Mitchell Simoens @LikelyMitch

    Check out my GitHub:
    https://github.com/mitchellsimoens

    Posts are my own, not any current, past or future employer's.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •