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?
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