If an array of length n contains k distinct values, I can do this:
1) Gather the first occurrence of each value into a contiguous buffer.
2) Divide the array into subarrays of length k and merge sort them, using the buffer as swap space.
3) Merge the subarrays with inplace_merge.
The first two steps can always be done in O(n log n). The third step seems to be okay when either k or n/k are bounded by a constant, but I’m not sure about the general case. Thinking some more.
If an array of length n contains k distinct values, I can do this:
1) Gather the first occurrence of each value into a contiguous buffer.
2) Divide the array into subarrays of length k and merge sort them, using the buffer as swap space.
3) Merge the subarrays with inplace_merge.
The first two steps can always be done in O(n log n). The third step seems to be okay when either k or n/k are bounded by a constant, but I’m not sure about the general case. Thinking some more.