Sunday, July 21, 2013

What is faster: std::sort or std::make_heap + std::sort_heap?

At first lets consider time complexity of algorithms.

Time complexity of std::sort.
According to the C++ standard, sort is required to perform O(NlogN) comparsions on average but has worst-case complexity of O(N*N), where N is last - first. This latitude, however, is unnecessary. It is possible to implement sort so that the number of comparsions, both average and worst-case, is only O(NlogN) [1].

Time complexity of std::make_heap.
Linear. At most 3N comparsions, where N is last - first.

Time complexity of std::sort_heap.
At most NlogN comparsions, where N is last - first.

Time complecity of std::make_heap +std::sort_heap in the worst-case is 3N + NlogN.

Performance testing.
Code below has been run on ideone.com with gcc 4.7.2. in testing purpose.


Performance testing results.
On reverse range std::sort can be slower than std:make_heap + std::sort_heap in 2 times.
==== Comparing std::sort vs std::sort_heap performance. ===
==== Range types: sorted, reversed, random  ===
==== Range size is 10000000.    ===

==== std::sort results:
Consumed time for sorted range: 0.340000 sec.
Consumed time for reversed range: 2.520000 sec.
Consumed time for random range: 1.110000 sec.

==== std::make_heap+std::sort_heap results:
Consumed time for sorted range: 1.060000 sec.
Consumed time for reversed range: 1.260000 sec.
Consumed time for random range: 4.660000 sec

Conclusions
std::sort can be slower then std::make_heap +std::sort_heap in N/(3 + logN) times in worst-case. But, in average std::sort is faster.

References
[1]. Generic Programming and the STL: Using and Extending the C++ Standard Template Library

 

4 comments: