heap_sort is unusably slow in debug mode, and 'effectively hangs' for large instances. This also in rare cases (and this is how I came across it) effects std::sort, which calls make_heap / heap_sort when it's quicksort partitioning is doing badly.

Consider sorting a vectors of zeroes in 4 ways:

1) std::sort
2) std::sort, -D_GLIBCXX_DEBUG
3) std::heap_sort
4) std::heap_sort, -D_GLIBCXX_DEBUG

1,000 elements: 0.004s, 0.014s, 0.004s, 1.3s
2,000 elements: 0.003s, 0.033s, 0.006s, 4.7s
5,000 elements: 0.005s, 0.096s, 0.008s, 32.7s
10,000 elements: 0.006s, 0.166s, 0.013s, 104s

We can see we've effectively changed an 'O(n log n)' algorithm into an 'O(n^2 log n)' algorithm.

Note, this problem is not fixed by filling the array with different numbers. 

Looking at pop_heap, it is just a thin wrapper over __pop_heap, along with this check. Therefore I believe the easiest fix will be to make sort_heap call __pop_heap directly, which avoids the check.

I tested this with the following program:

#include <algorithm>
#include <vector>

using namespace std;

int main(void)
{
  vector<int> a(5000, 0);
#ifdef HEAP
  make_heap(a.begin(), a.end());
  sort_heap(a.begin(), a.end());
#else
  sort(a.begin(), a.end());
#endif
}