How long does it to sort 2.5 million numbers using HeapSort?

Question

I have 2.5 million entries/numbers, which I am using HeapSort to sort them by inserting in a sorted heap. But it is taking for ever.. I know heapsort running time is O(nlogn) but in real life, on a basic computer, how much time are we talking about here? I have 8 G.B. of RAM on my Windows machine, but I have dual-booted Ubuntu which I believe is chosen to run with 1 G.B of RAM.

It took less than 15 seconds for 15,000 numbers. so proportionally speaking, will it take about 40 minutes?

Answer 1

For a rough estimate, assuming no additional memory related overhead when scaling from 15k to 2.5 million, the runtime will be: (2.5m * log(2.5m)) / (1.5k * log(1.5k)) * 15 seconds = 64 minutes

Answer 2

I don't know about heap sort and my eyes pop out when I'm looking at the original asker sorting 15 seconds for 15,000 numbers, or the accepted answer that accounts for that, but the default C++ STL sort of a vector of 2.5M integers takes me < 100ms. Compiled with -O3, of course, if not: < 700ms.