What I'll do is use up yet more memory to convert the array of pointers to an array of ELEM whose first part is the fixed-digit key and the second part is the original pointer. I'll then dfr that like normal, and finish by copying the pointers back in the sorted order.
This is an effort to make it easier for people who want to do that without just making them change how they store their data, which is a bit uncool for me to do.