Comment by veyron

scorchin posted the implementation of nth_element, except he forgot to look at how the gnu implementation of __introselect behaves.

If you look there, you will see it internally uses a heap.