Hello!
I wanted to submit a re-implementation of alexandria:median. Currently the function works by fully sorting the sequence, which has a complexity of O(n log n). In the attached patch I provide an implementation as a special case of the quick select algorithm, which brings its complexity down to O(n).
The new implementation is more complicated, though I think it's still simpler than some other algorithms in alexandria. Anyways, the performance gains are dramatic enough that I thought I'd at least submit the patch. I did some testing via the timing code in median-timing.lisp, and observed speedups of 5-10x even on sequences with just 100 elements.
I could also provide the quick select algorithm as its own function if there's any interest, though I'm not sure what the appetite for adding new features is.
- Anish Moorthy
