I recently learned how to use heaps and the beauty of heapsort. I decided to compare heapsort with std::sort in C++ and Arrays.sort() in Java. I sorted an array of integers, each randomly generated in the range of <0; 2000000000)
I generated 100,000,000 integers into an array in Java, and ran Arrays.sort(), then generated new random sequence and ran my heapSort(). This is an output of my program in Java:
Arrays.sort time: 10.923 seconds.
Heap sort time: 1.402 seconds.
So heapsort is about 8 times faster.
I then ran similar code in C++, this time using std::vector as my container (due to the fact that std::sort needs two iterators).
C++ results:
Heapsort: 3.213
std::sort: 37.264
So in my program, std::sort is about 12 times slower.
In Java, I measured time using System.currentTimeMilis() and in C++ I used clock() from .
This was tested on Windows 7, Quad-Core Intel i5 2500k, overclocked to 4.8GHz. C++ was compiled with -Wall -pedantic
flags.
Can anyone tell me what is going on? Is heapsort really that much faster? Or did I make an mistake in my code? I don't want to flood this post with lots of code, so I will link it at the end of this post.
BTW: Yes, I'm aware that Arrays.sort() is stable and heapsort isn't. Java doesn't have an unstable sort (atleast, I haven't found one). That is why I used std::sort in C++, to see if it had something to do with stability or not.
Source code, both C++ and Java: https://gist.github.com/anonymous/7475399
int tmp = heap[0]; heap[i] = heap[0]; heap[i] = tmp;
– Darthfett Nov 14 '13 at 22:32Arrays.sort()
is overloaded. For an array of builtin type the implementation is permitted to use a non-stable sort, but for an array ofObject
type it must be stable. So, if the implementation chooses to use a stable sort algorithm even for builtin types, you cannot be blamed for comparing it against heapsort. – Steve Jessop Nov 14 '13 at 22:33