I read the paper. Seems like they can not beat a median pivot (that takes O(k) to find at each step, but keeps the quicksort runtime of O(n log n).)

Still, a cool progam.