[Home]
HeapSort

| CodeRaptors | Projects | Tips and Scripts | Guides | Links |


Each colored bar represents a list element. The height and color correspond to the value of the element. The green bar signals a read operation and the blue one a write operation.

Virtual time is a rough estimate of the algorithm speed. It can be used to compare the different algorithms on this website, but it's not really a good benchmark. The actual running time of the applet is not related to the virtual time and says nothing about the speed of the algorithm, it is trimmed to make the slower ones bearable to watch and the faster ones possible to see.

The heapsort algorithm has complexity O(n log(n)) where n is the number of elements. It has no worst case scenarios so it always runs fast, but generally slower than Quicksort and for almost sorted lists a lot slower than simpler algorithms. Thanks to the upper bound on running time it's safer than Quicksort, but it can't be parallellized.

This particular implementation is an in-place heapsort. It uses the left part of the list to build and maintain a heap and then it uses that heap to create the sorted list on the right part. A reverse sorted list is already a heap, try pressing "reversed" above and you'll see!

More on Heapsort here.

<< Go back to the sorting algorithms



Search: