score:0

Accepted answer

The radix sort invariant is that the data is sorted using the first k bits. If you want an operation that adds more data sorted or not, you are asking for merge sort functionality not radix. If what you are adding is bits of data to all records you could use a monoid.

Edit: The hart of a monoid is an associative operation. We can look at the sorting bits as a way of applying partial order. You injest the data for all records bit by bit. Each bit applies a partial order. This is associative you can merge some bits to get a more elaborate partial order. Note order is important but it is still associative.and thus can be.viewed as a monad

score:0

I think you may be thinking too literally about the idea of radix sort. Abstractly, I imagine the monoid you want is

  1. Sorted lists with
  2. Merging

The big question is how you want to represent the sorted lists. If you represent them as sorted Haskell lists, then the merge operation is the usual piece-by-piece merge used in merge sort. If you represent them in a more "radixy" fashion, then you'll have some variety of trie. You can probably find some algorithms around for merging tries. There's one in bytestring-trie, but nothing about its implementation seems to be documented.


Related Query

More Query from same tag