Imagine that you make your living in a somewhat unorthodox but honest way: you live in a tent outside of the castle and every morning, as the king walks into the castle, he hands you a deck of cards. "I've just played cards last night," he says "and I'm going to again tonight, and I'd like these cards ordered and sorted by suite and number by this evening." Then the king goes into his castle and does whatever it is that kings do in castles all day.

So, you take this deck of cards, which is in any old order, as the king just played with it last night, and you set about sorting it. Now, you've been doing this a long time, and your methodology has improved over the years. When you started, you would just lay the cards out in the order the king gave them to you, and then start at the beginning of the line and ask "is this card greater than the next?" and move the two cards in response to the answer so that the two are in order. You would continue this process, repeating from the beginning of the line, until you made a complete pass through the line without making any changes. Sometimes, this took you all day, sometimes you would even make the king wait for you to finish, and that made him very angry, which is very bad.

Your sorting process is compounded by the limitation of your ability to read and compare the value of two cards, because you don't really know how to read or add, it takes you about ten seconds to decide if a card is greater than or less than another card. For a 52 card deck, this means your original sorting method would require 52 times 52 comparisons, or, in real time, seven and a half hours of non-stop work, leaving you no time to do anything else.

Over the years of doing this job for the king you discovered some shortcuts that would take less time but still produce a sorted deck, despite your limited ability to read and understand the values of the cards. While that still takes ten seconds, your new deck sorting approaches require 52 times 1.7 comparisons, or in real time, about fifteen minutes. This is much, much, better than before, but it would of course be better still if it took even less time, as you have discovered that you can now use this extra time to sort cards for all the other members of the court.

One day a traveling wizard observes you sorting cards and says "you know, this method that you have for sorting cards is quite clever but what if I were to tell you that you could sort these cards in 8.6 minutes flat?" This is about half the time it takes you right now, meaning that you could double the number of decks you sort in a day, doubling your income. You are very interested! "Tell me more," you tell the wizard. "Here, read this paper" the wizard replies, and they give you the paper GP linked.

er, given the specific example used, I would expect the wizard to say "look, you know exactly what the cards are, why don't you buy your own sorted deck of cards and staple them to the floor of your tent. Then when the king gives you a deck, just put each card on top of the matching one, then scoop them all up together in order." to which you would of course reply "but my tent is too small!", and the wizard would say "then just put down one of each number of one suit, plus the other 3 aces. Then pile all the cards on the aces first, just by matching suit, and finally take each of those piles in turn and do it by number."

Now, I haven't read the paper, but my guess is that the next objection is "but the king keeps switching the suits! Yesterday, they were diamonds, today they're little squiggly sketches of soft-serve poop! Which he pays me well enough to not think too hard about!" and the wizard would go on to explain that as long as you ask what the suits and numbers are in advance, you can make piles for them. Or something.

Sorry, usually I try to read papers before commenting, but I've gotta run -- I hear that whining noise that usually means my poop dispenser's jammed again.

quite the catch at the end. The wizard probably talked about teaching a man to fish, too.

ELI5 Edition: Basically everything uses sort (either to rank things or to set up search), so improvements to sort improve basically everything.

Explaining it in further detail like you're a fellow member of our industry:

Edge computing advances are pretty important right now, since the amount of data we're working with on the edge of the network is growing very quickly. Advances in how we compute backpropagation (essentialy using a right-recursive process for the Chain Rule) mean that we can do machine learning on 2015-level phone gpus, rather than 2015-level desktop GPUs.

This advance hints at a promise of similar gains. With care, you can sort much faster. What's more, your sorts and your merge of decomposed sorts is roughly the same cost now. And multiple, layered sorts don't require custom logic or clever functional programming (at the edge developer's model) to compose.

Essentially you pick what fields in complex (maybe even nested) data structures to sort by, in what order, and the system makes a sort.

Why does this matter? Well, it will make nearly all data structures Just Faster; many of them secretly rely on ordered and sorted arrays. It makes it easier for distributed systems authors to make queryable systems (it's pretty easy to write a discriminator or specify a discriminator function remotely and then use that on the fly, as opposed to a comparator).

One place in the client-software world where it can have big impact is offline webapps. Right now, it's almost always cheaper to call out to a remote datastore rather than use a local datastore even if you're using sqlite under the covers because of the cost of synchronizing sqlite's data model. A discriminator-based approach would let you do complex queries of data in memory, but that data could still be themselves commutative data types that are coalescing data out of a data stream (or multiple data streams) remotely.

It's also worth noting that another really cool paper from this year improving on the HAMT trie (https://michael.steindorfer.name/publications/phd-thesis-eff...) could also benefit from this approach, which means all of us using immutable data structures can continue to do so with MUCH better performance characteristics but continued thread safety.

> Essentially you pick what fields in complex (maybe even nested) data structures to sort by, in what order, and the system makes a sort.

Wait, is that it? What makes this novel?

What's novel is projecting that operation efficiently into a field where radix sort can operate on all the discrimination at once.

Can you give an example where the obvious method is inefficient, and what this would do?

I just wanted to give you a taste of how this works in an ungeneralized way before I went. Linear time algorithms are fast and feel very different. I want to stress this is not directly related to the technique in the paper, but is in the same "family" of algorithms, and is very easy to understand.

Imagine you're doing the classic "write an algorithm to determine if one word is the anagram of another". The classic solution is to sort and compare the strings to be checked.

We can do this pretty elegantly for strings without using quicksort. It goes like this: allocate a block of 26 bytes. Each byte is a counter for a letter in that position (0 -> A, 1 -> B, ...). Now sweep across the string, and each time you see a letter, increment that number. If you really care hard, you can go crazy with SIMD and other clever tricks here.

Once you're done this for 2 strings, you need only compare the two regions for equality (a constant time operation).

The worst case, average case, and minimum running time of this algorithm is O(len_word_1+len_word_2)+c, and because we can safely make assumptions about the length of the strings (no word in anym ISO-Latin-1 encoding exceeds 255 of any character), we can do it fairly compactly. This is MUCH faster and can be done with perfect memory safety (which is to say, it is optimal with mutability but all operations are commutative so they may be subdivided, done in any order, and recombined at will).

Try implementing this. It's really, really fast on modern hardware. Especially if you're working it out for a full /usr/share/dict/words file on a normal _nix/bsd installation.

We can even see that composability feature in our current problem! Imagine we have have that big dictionary file and we want to find ALL the anagrams in it. Imagine we start cutting the above technique in half and computing the byte vector for every word in the dictionary (which is O(n) time). If we sort THESE vectors, we could just pick out all the equal values and say "There are the anagram groups", right?

If we were to insert them into some very wide trie (as is the style these days), that'd be O(Numwords * log(numwords)), which is really just sorting again. We'd do it in minimum 2 passes with O(n log n) cost. But if we have composable discriminators we could do this in one big pass with O(n) cost! Our constant factors would grow because we're dealing with more memory. We could then not only sweep across the sorted list to extract groups (note the symmetry with the ABC counter approach above), but we could also pretend it's a tree structure (start at the length/2 element in the list and pretend its a binary tree) and search for new items inside the block, so we could check for new word anagrams subsequently in O(log n) time.

The paper I linked talked about generalizing this idea (a special case of radix sort) and making it composable.