What is a fast way to merge sorted subsets of an array of up to 4096 32-bit floating point numbers on a modern (SSE2+) x86 processor?
Please assume the following:
- The size of the entire set is at maximum 4096 items
- The size of the subsets is open to discussion, but let us assume between 16-256 initially
- All data used through the merge should preferably fit into L1
- The L1 data cache size is 32K. 16K has already been used for the data itself, so you have 16K to play with
- All data is already in L1 (with as high degree of confidence as possible) - it has just been operated on by a sort
- All data is 16-byte aligned
- We want to try to minimize branching (for obvious reasons)
Main criteria of feasibility: faster than an in-L1 LSD radix sort.
I'd be very interested to see if someone knows of a reasonable way to do this given the above parameters! :)