algorithms to split data into roughly equal sized quantiles
It is possible to find the quantiles in $O(N)$ using a straightforward modification of the selection algorithm based on quicksort (see http://en.wikipedia.org/wiki/Selection_algorithm).