Hi John, I played the radix sort again during the weekend.
First, I changed my direction and implemented the in-place switching in the other way, where I did a way like chained-switching. Say starting from item0, for example, switching item0 to item5, then check where item5 should be switched to, and makes the switch, till an item is switch to position 0. See my implementation in other-implemation.diff if you are interested in it. This time, I eyeball checked the sort result and confirmed the correction. But my implementation is slightly slower than your implementation, based on the same test procedure I described in my previous email, my implementation is roughly ~3% slower your implementation. So I think that at least proves your current implementation in v5 has been perfectly fine tuned. Then I went back to read your implementation again, I found a tiny optimization, where we can move “count sorted partitions” to before the “for” loop, which avoid sorted partition to go through the “for” loop, and my test shows that the movement may lead to ~1% improvement. See the change in radixsort_tiny_optimizeation.diff. I also noticed that, there could be cases where target element is already in the right partition, so that switching could be unnecessary. However if we want to avoid such unnecessary switches, then we will need to add a “if” check. Given the total number of such cases is tiny, the “if” check would be more expensive than performing blindly switching. I tried to add such a check like: ``` if (offset == (size_t) (st - begin)) continue; /* already in correct position */ ``` With my test, it just makes the query ~3% slower. So, now I think I can wrap up this round of playing. My only suggestion is radixsort_tiny_optimizeation.diff. I may revisit this patch again once you make the entire patch set ready for review. Best regards, -- Chao Li (Evan) HighGo Software Co., Ltd. https://www.highgo.com/
other-implemation.diff
Description: Binary data
radixsort_tiny_optimizeation.diff
Description: Binary data
