Collapse Sort

While applying for a software engineering position ten years ago, I was asked to implement the quicksort algorithm. Fortunately, my interviewer was gracious enough to provide me with a refresher of how the quicksort algorithm worked. I somehow managed to muddle my way through to a relatively acceptable solution to the problem. I’m sure that my implementation of the algorithm was neither quick nor a sort algorithm. Discuss along with the Holy Roman Empire.

Years later, I’ve since pivoted away from C/C++ and now find that the majority of my work is in the rather uninhibited world of JavaScript. In my first frontend related gig, I found myself helping to debug a piece of code that did something like this:

const someArray; // defined elsewhere
const lastValue = someArray[someArray.length];

(I’m paraphrasing a lot here)

Given that arrays in JS start at 0, this should be corrected to const lastValue = someArray[someArray.length - 1]. To my surprise, however, lastValue didn’t explode with a seg fault, out-of-bounds, index error, etc. It just continued to plug away in stoic silence, with the value of lastValue being undefined. I filed this away as an annoying curiosity for the time being.

The Discovery

Later that same year, I was mulling over the concepts of sorting and just noodling around in a browser developer console window when I wrote the following:

sort = A => A.reduce((B, x) => (B[x] = x, B), []).filter(x => x);

sort([2, 7, 1, 8, 28, 18])
// [1, 2, 7, 8, 18, 28]

Now, take a careful look at this “algorithm”. Before I explain what it’s doing, try to analyze it as an exercise to the reader. Ask yourself the following questions:

• What is the Big O Little O What Begins with O?
• Will this work for all numbers?
• What are the situations in which this kind of sort will fail?

Why does it work?

Let’s first give a brief breakdown on the overall code flow.

The key reason this works is that Javascript arrays are dynamic in nature. If we have an array of 3 elements ["A", "B", "C"] and we try to set a value “X” at position 5, the array is automatically resized to a length of 6, i.e. ["A", "B", "C", undefined, undefined, "X"]. Since we are positioning our unsorted elements at indices equal to their actual element value, you end up with an almost sparse-like sorted array.

[6, 1, 2] -> [undefined, 1, 2, undefined, undefined, undefined, 6]

Then, we can collapse the array by simply stripping out the undefined value elements and we’re done. Unusually, the Big O is more influenced by the largest element’s value rather than the number of elements in the unsorted array.

What are the limitations?

⚠️ Spoilers ahead.

Duplicate elements

collapseSort([1, 6, 1, 8])
// result [1, 6, 8]

The fix

collapseSort = A => A.reduce((B, x) => (B[x] = [...(B[x] || []), x], B), []).filter(x => x).flat();

Bonus points, we’re guaranteed significantly faster runtimes since the interpreter only has to evaluate a single line of javascript! :p However, if you’re working for a large company, this could also negatively impact your Jellyfish LOC metric, in which case here’s an expanded look at what’s going on:

const collapseSort = (A) => {
    const B = A.reduce((acc, curNum) => {
        // Create / append to a bucket at the index of current number
        acc[curNum] = [...(acc[curNum] || []), curNum];
        return acc;
    }, []);

    // Flatten the array and filter out empty slots
    const flattenedAndFiltered = B.filter(element => element).flat();

    return flattenedAndFiltered;
};

Negative values

Since we are treating the values of the unsorted array as “indices”, it’s obviously going to fail pretty spectacularly if we attempt to access negative indices in the array. Astute observers would have also realized that the very first algorithm would have also failed for 0 values since it is not considered truthy.

const integersCollapseSort = (A) => {
    // use a max to offset all the values to positive indices
    const max = Math.abs(Math.min(...A));

    const B = A.reduce((acc, curNum) => {
        // Create / append to a bucket at the index of current number
        acc[curNum + max] = [...(acc[curNum + max] || []), curNum];
        return acc;
    }, []);

    // Flatten the array and filter out empty slots
    const flattenedAndFiltered = B.filter(element => element).flat();

    return flattenedAndFiltered;
};

Further Expansion

As an exercise to the reader, we have left off how this could be adapted to support floating point numbers, imaginary numbers, undiscovered numbers, intersectional numbers on cartesian planes oriented at perpendicular angles with each other, and lonely numbers.