why in reverse sorting is faster, than re-sorting

Question

I wrote such a test -

std::vector<int> test_vector;                                                        

for (int i = 0; i < 100000000; ++i) {                                                
    test_vector.push_back(i);                                                        
}                                                                                    

QElapsedTimer timer;                                                                 
timer.start();                                                                       

std::sort(test_vector.begin(),test_vector.end(), [](int a, int b) { return a < b; });

qDebug() << "The slow operation took" << timer.elapsed() << "milliseconds";          
qDebug() << "The slow operation took" << timer.nsecsElapsed() << "nanoseconds";

here i start re-sorting and the result

The slow operation took 4091 milliseconds
The slow operation took 4091842000 nanoseconds

but when I changed

std::sort(test_vector.begin(),test_vector.end(), [](int a, int b) { return a > b; });

result

The slow operation took 2867 milliseconds
The slow operation took 2867591800 nanoseconds

i tested on Qt_5_12_3_MinGW_64_bit-Release , and can't understand why in reverse sorting is faster, than re-sorting?

Resolved!

I tested the same example on Qt_5_12_3_MSVC2017_64bit and the issue is resolved, the problem was in MinGW_64

However, I still have a question, why if I sort the vector into a feed all the elements of 10,

#include <chrono>
#include<iostream>
#include <vector>
#include <algorithm>



    int main() {

        std::vector<int> test_vector;

        for (int i = 0; i < 100000000; ++i) {
            test_vector.push_back(10);
        }

        auto begin = chrono::high_resolution_clock::now();

        std::sort(test_vector.begin(), test_vector.end(), [](int a, int b) { return a < b; });


        auto end = std::chrono::high_resolution_clock::now();
        auto dur = end - begin;
        auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(dur).count();
        std::cout << ms << endl;


        return 0;
    }

result 167 milliseconds,

and re-sorting 2553 milliseconds

for (int i = 0; i < 100000000; ++i) {
        test_vector.push_back(i);
    }

Are these two distinct tests, or are you doing both tests one after the other in the same run? — François Andrieux, Jul 23 '19 at 15:01
Quicksort has worst-case efficiency O(n^2) when data is already sorted. If your standard library implementation uses this algorithm, the results are explainable (note - from C++11 the complexity is required to be at most O(n*logn), so this won't be the right explanation for modern C++) — Yksisarvinen, Jul 23 '19 at 15:03
Also, how are you building the code? What optimization level is used, etc... — Yksisarvinen, Jul 23 '19 at 15:07
@Yksisarvinen I'm testing the code on QT creator Qt_5_12_3_MinGW_64_bit-Release, and in both cases I use this code in Release build — Vahagn Avagyan, Jul 23 '19 at 15:15
I tested the same example on Qt_5_12_3_MSVC2017_64bit and the issue is resolved, the problem was in MinGW_64, — Vahagn Avagyan, Jul 23 '19 at 15:48
However, I still have a question, why if I sort the vector into a feed all the elements of 10, I get 160 milliseconds, and re-sorting 2455 milliseconds? — Vahagn Avagyan, Jul 23 '19 at 15:52
Your problem is that std::sort is faster on structured data than it is on random data. This can have two sources: (1) The std::sort implementation, which may be optimized for cases like sorted / reverse-sorted data, and (2) branch prediction, which allows the processor to work pretty efficient on structured data (see https://stackoverflow.com/a/11227902). — pschill, Jul 23 '19 at 16:35

why in reverse sorting is faster, than re-sorting

Resolved!

0 Answers0