You might get some milage out of partitioning on k, make k hashtables, for n, hash n/k into the n%k table. then just look for adjacency. doesn't improve the wor

You might get some milage out of partitioning on k, make k hashtables, for n, hash n/k into the n%k table. then just look for adjacency. doesn't improve the worst case at all, k=1, or all n's fall in the same bucket, but in the average (maybe? no idea about the actual data) case it would help with collisions, or reducing the size of the sorted arrays. Also, it becomes embarrassingly parallel. A trivial next step is one thread per hashtable. Of course, all that overhead might be a big waste of time.