matrix quicksort.js

    function vecswap(xs, a, b, c) {
        var n = Math.min(b-a, c-b),
            i = a,
            t, j;
        for(j = c - n, i = a; j < c; j += 1, i += 1) {
            t = xs[i]; xs[i] = xs[j]; xs[j] = t;
        }
        return a + (c - b);
    }
    //STARTSORT
    function matrixQSort(matrix, checkInvariant) {
        var rows = [],
            i, N = matrix.length,
            numColumns = matrix[0].length;

        // Set up an indirection array.
        for(i = 0; i < N; i += 1) {
            rows[i] = i;
        }

        sort(rows, 0, 0, N);
        return rows;

        // The sort body.
        function sort(rows, column, start, end) {
            // End the recursion if there is only one row left to
            // consider, or if we are past the last column.
            if(end - start < 2 || column === numColumns) {
                return;
            }
            var i = start - 1,
                j = end,
                u = start,
                v = j,
                pivotRow = rows[Math.floor((start + end) / 2)],
                pivot = matrix[pivotRow][column],
                t;

            if(end - start > 20) {
                // Do a median of three if there are more
                pivot = medianOfThree(matrix[rows[start]][column],
                                      pivot,
                                      matrix[rows[end-1]][column]);
            }

            // Reorder the values, and maintain the indices so we have
            // the following:
            //
            // begin (inclusive)  |  end (exclusive)  |   description
            // start              |  u                |   == pivot
            // u                  |  i                |    < pivot
            // i                  |  v                |    > pivot
            // v                  |  end              |   == pivot

            while(i < j) {
                i += 1;
                while(i < j && matrix[rows[i]][column] < pivot) {
                    i += 1;
                }

                j -= 1;
                while(i < j && pivot < matrix[rows[j]][column]) {
                    j -= 1;
                }

                if(i < j) {
                    t = rows[i]; rows[i] = rows[j]; rows[j] = t;

                    // Maintain the fat partition by moving equal
                    // values out the ends.
                    if( pivot === matrix[rows[j]][column]) {
                        v -= 1;
                        t = rows[j]; rows[j] = rows[v]; rows[v] = t;
                    }
                    if(matrix[rows[i]][column] === pivot) {
                        t = rows[i]; rows[i] = rows[u]; rows[u] = t;
                        u += 1;
                    }
                }
            }

            if(i === j && pivot === matrix[rows[i]][column]) {
                t = rows[i]; rows[i] = rows[u]; rows[u] = t;
                u += 1;
                i += 1;
            }
            if(checkInvariant) {
                (function() {
                    var k;
                    function check(result) {
                        if(!result) {
                            throw 'check failed';
                        }
                    }

                    for(k = start; k < u; k += 1) {
                        check(matrix[rows[k]][column] === pivot);
                    }

                    for(k = u; k < i; k += 1) {
                        check(matrix[rows[k]][column] < pivot);
                    }

                    for(k = i; k < v; k += 1) {
                        check(matrix[rows[k]][column] > pivot);
                    }

                    for(k = v; k < end; k += 1) {
                        check(matrix[rows[k]][column] === pivot);
                    }
                }());
            }

            // Now, 'flip' the sides around to bring the values equal
            // to the pivot to the middle.
            j = vecswap(rows, i, v, end);
            i = vecswap(rows, start, u, i);

            if(checkInvariant) {
                (function() {
                    function check(result) {
                        if(!result) {
                            throw 'check failed';
                        }
                    }

                    var k;
                    for(k = start; k < i; k += 1) {
                        check(matrix[rows[k]][column] < pivot);
                    }

                    for(k = i; k < j; k += 1) {
                        check(matrix[rows[k]][column] === pivot);
                    }

                    for(k = j; k < end; k += 1) {
                        check(matrix[rows[k]][column] > pivot);
                    }
                }());
            }

            // Sort the rows that matched the entry, but step them to
            // the next column.
            sort(rows, column + 1, i, j);

            // Sort the things that were not equal to the pivot still
            // using the same column.
            sort(rows, column, start, i);
            sort(rows, column, j, end);
        }
    }