**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.520000sec. 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.260000sec. 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

This is exactly what I was looking for. :)

ReplyDeleteI am glad to hear that :)

ReplyDeletethank. I was looking a test :)

ReplyDeleteWelcome :)

ReplyDelete