3 ms·
I feel that radix sort would be a better choice, and maybe faster as well. MSB in-place radix sort can sort an arbitrary range, which can be used to find the me
by gorset 15y ago
I feel that radix sort would be a better choice, and maybe faster as well. MSB in-place radix sort can sort an arbitrary range, which can be used to find the median very quickly. You simply count the elements for each buckets, and then continue with the bucket containing the median value.
Of course, this requires 0 comparisons (but you might want to to a insertion sort for the final round), and a maximum of 4 rounds for 32 bits numbers using 8 bits buckets.
- xyzzyz 15y agoThe thing is, you do not always want to find a median of a set of integers -- not even most of the time. Frequently you want to find a median of floats, or use a custom ordering. Real life is not so simple.
- gorset 15y agoFloats doesn't complicate radix sort that much. To quote McIlroy et al. (1993) "the troubles with radix sort are in implementation, not in conception". Finding the median strikes me as more of a academic problem than a real life problem. However, partial sort (for which finding the median is a sub problem) is an easy optimization relevant for search engines, where you sometimes only need to extract the hits from position 1000-2000.