Best sort approach for small data sets
Here are two ideas. It's hard to say whether they're any good - you'll have to implement them.


Use (randomized or deterministic) QuickSelect in order to find the median, and then find the bottom half with a single scan. 
Use some hard-coded sorting network, e.g. Batcher, bitonic or pairwise. If there is some hardware support for the basic operation of sorting two memory cells, then this can be pretty fast (even though you're not using parallelism). You can also try to come up with your own sorting network that only sorts in your sense - perhaps trimming one of the ones I listed would do.