Comparison of Four Algorithms for Selecting the N-Smallest Values

TL;DR -- Maintaining a small heap wins. Quicksort-style selection loses. Summary results appear at the end of the article.

Maintaining a small heap takes 105,714 to 106,452 comparisons.

Building a big heap takes 166,525 to 166,629 comparisons.

Quick select followed by a second pass takes 222,351 to 496,865 comparisons (widely variable results depending on lucky or unlucky pivots).

Quick select with intermediate small concatenated sorts takes 131,171 to 217,504 comparisons.