# [racket] Looking for feedback on code style

Noel Welsh wrote:
>* I think this is great code -- very clear. For production use you have
*>* the wrong data structure (Lists are O(n) random access and length; you
*>* want O(1) vectors), but that doesn't matter for your use.
*
I don't think vectors help very much in this case (median-finding). For
the given code, the O(n) access to the middle of the list is dominated
by the cost of the sorting, which is at least O(n log n) [*].
It is theoretically possible to compute the median in O(n) time, but the
method is complicated and not very practical. But sorting definitely
does too much work. If only the median (or the kth largest, a problem
called "selection") is needed, a method which is both practical and of
pedagogical interest stems from adapting Quicksort, which is a good
exercise after section 25.2 of HtDP. This has expected cost O(n) on
random data, and vectors offer no asymptotic advantage over lists. --PR
[*] Technically, "at least Omega(n log n)".