It's worse case linear, as used for sorting it beats the Go standard library on the average and worst cases, lagging a bit on the best cases.
In my experience, median-on-ninthers (which is only slightly more complicated than median-of-medians) definitely beats both heap sort and particularly heap select as a fall back for the degenerate case.
And it's not just academic: I've sped up significant stuff at work by switching from sorting to partial sorting and/or selection.
This one is just not true. Here it is in 255 lines of well commented Go code: https://github.com/ncruces/sort/blob/v1.0.3/quick/quick.go
It's worse case linear, as used for sorting it beats the Go standard library on the average and worst cases, lagging a bit on the best cases.
In my experience, median-on-ninthers (which is only slightly more complicated than median-of-medians) definitely beats both heap sort and particularly heap select as a fall back for the degenerate case.
And it's not just academic: I've sped up significant stuff at work by switching from sorting to partial sorting and/or selection.