JavaScript Quicksort

Quicksort, yet again. This time, in JavaScript!

I have been using JavaScript more frequently, and have been pleasantly surprised at how fast it is.

So, I naturally wanted some test cases of things that I always thought JavaScript was too slow for. Sorting was one of those cases.

To check it out, I wrote some quicksort functions and compared them to Array.sort. Here is the unscientific comparison.

Using Engineering a Sort Function as a reference, along with textbooks, etc, I wrote the following:

function qsort1(xs, start, end) {
    start = start || 0;
    if(end === undefined) { end = xs.length;}

    if(end < start + INSERT_SORT_THRESHOLD) {
        isort(xs, start, end);
        return xs;
    }

    let i = start - 1,
        j = end;
        // pidx = Math.floor(Math.random() * (end - start)) + start,

    const pivot = medianOfThree(xs[start],
                                xs[Math.floor((start + end) / 2)],
                                xs[end-1]);
    while(i < j) {
        i += 1;
        while(i < j && xs[i] < pivot) {
            i += 1;
        }

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

        if(i < j) {
            const t = xs[i];
            xs[i] = xs[j]; xs[j] = t;
        }
    }
    if(xs[i] < pivot) { throw 'invariant'; }

    qsort1(xs, start, i);
    qsort1(xs, i, end);
    return xs;
}

This method:

• Uses a median of three pivot strategy

• Leave the pivot in place while partitioning

• Is recursive down both halves of the partition.

Lines 18 – 32 partition the data.

Originally, I used a random pivot. That works well, but the median of three can help partition the data more evenly, leading to less work.

The pivot value is copied out to a temporary during the partitioning. In JavaScript, this isn't as big of a deal, because objects besides primitives are basically reference types anyways … so copying the pivot value in that case is more like a pointer copy.

A common case that I care about is when there are many equal values in the array. This version of quicksort does not handle that well.

The next version uses the fat partitioning described in the paper to group all of the values equal to the pivot.

function qsort2(xs) {
    sort(xs, 0, xs.length);
    return xs;

    // The actual sort body.
    function sort(xs, start, end) {
        if(end < start + INSERT_SORT_THRESHOLD ) {
            isort(xs, start, end);
            return;
        }

        let i = start - 1,
            j = end,
            u = i,
            v = j;
        const pivot = medianOfThree(xs[start],
                                    xs[Math.floor((start + end) / 2)],
                                    xs[end-1]);
        // 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 && xs[i] < pivot) {
                i += 1;
            }

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

            if(i < j) {
                const t = xs[i];
                xs[i] = xs[j]; xs[j] = t;
                /* jshint ignore:start */
                // We are ignoring the !.  Just trying to stick
                // with < for now...
                if(!(xs[i] < pivot)) {
                    u += 1;
                    const t = xs[i];
                    xs[i] = xs[u]; xs[u] = t;
                }
                if( !(pivot < xs[j])) {
                    v -= 1;
                    const t = xs[j];
                    xs[j] = xs[v]; xs[v] = t;
                }
                /* jshint ignore:end */
            }
        }

        // if(xs[i] < pivot) { throw 'invariant'; }

        // Now, 'flip' the sides around to bring the values equal
        // to the pivot to the middle.

        j = vecswap(xs, i, v, end);
        i = vecswap(xs, start, u + 1, i);

        // xs[i] >= pivot.
        sort(xs, start, i);
        sort(xs, j, end);
    }
}

Lines 45 – 52 swap values equal to the pivot to the outer part of the array. At the end of the partition the pivot values are brought back together in the center.

These sort routines use the < operator. The Array.sort routine requires a comparison operator that returns -1, 0, or 1 for less than, equal to, and greater than. The custom routines are less general (so far!)

Here are some timing results on Chrome comparing the two sorts and the system sort. These tests are unfair and likely misleading, but they are a start.

1

The values in the array are 0, 1, 2, 3, 0, 1, 2, 3, … the whole way to the end of the array.

qsort1 and qsort2 are far less generic than Array.sort, and there are likely several errors in how I am doing this timing. Sometimes, for example I seem to be getting GC pauses while doing the test, but I have not confirmed what is going on yet. Overall, I am optimistic that in these cases, JavaScript can be made to run in a reasonable amount of time. Overall, the timing is pretty variable. That will be worth investigating before too long.

The NumPy values are in there for comparison. I am assuming that the NumPy sort is in native code underneath, and it is far easier to time python code than to write some C++ wrappers just for a comparison.

Here is a link to the test driver that launches directly into the tests.