Why is Python sort faster than that of C++
Question: Sorting a list of ints in python 3 seems to be faster than sorting an array of
ints in C++. Below is the code for 1 python program and 2 C++ programs that I
used for the test. Any reason why the C++ programs are slower? It doesn't make
sense to me.

\----- Program 1 - python 3.4 -----

    
    
    from time import time
    
    x = 10000
    y = 1000
    
    start = time()
    
    for _ in range(y):
        a = list(range(x))
        a.reverse()
        a.sort()
    
    print(round(time() - start, 2), 'seconds')
    

\----- Program 2 - c++ using sort from algorithm ------

    
    
    using namespace std;
    #include <iostream>
    #include <algorithm>
    
    int main(){
    
        int x = 10000; 
        int y = 1000;
        int b[10000];
    
        cout << "start" << endl;
    
        for (int j = 0; j < y; j++){
            for (int i = 0; i < x; i++){
                b[i] = x - i;
            } // still slower than python with this clause taken out
    
            sort(b, b + x); // regular sort
    
        }
    
        cout << "done";
        system("pause");
    }
    

\----- Program 3 - c++ using hand written merge sort ------

    
    
    using namespace std;
    #include <iostream>
    
    void merge(int * arr, int *temp, int first_start, int second_start, int      second_finish){
    
        int a1 = first_start, b1 = second_start, r = 0;
    
        while (a1 < second_start && b1 < second_finish){
    
            if (arr[a1] < arr[b1]){
                temp[r] = arr[a1];
                a1++; r++;
            }
            else {
                temp[r] = arr[b1];
                b1++; r++;
            }
        }
        if (a1 < second_start){
    
            while (a1 < second_start){
                temp[r] = arr[a1];
                a1++; r++;
            }
        }
    
        else {
            while (b1 < second_finish){
                temp[r] = arr[b1];
                b1++; r++;
            }
        }
    
        for (int i = first_start; i < second_finish; i++){
            arr[i] = temp[i - first_start];
        }
    }
    
    void merge_sort(int *a, int a_len, int *temp){
        int c = 1, start = 0;
        while (c < a_len){
            while (start + c * 2 < a_len){
                merge(a, temp, start, start + c, start + c * 2);
                start += c * 2;
            }
            if (start + c <= a_len){
                merge(a, temp, start, start + c, a_len);
            }
            c *= 2; start = 0;
        } 
    }
    
    int main(){
    
        int x = 10000; // size of array to be sorted
        int y = 1000; // number of times to sort it
        int b[10000], temp[10000]; 
    
        cout << "start" << endl;
    
        for (int j = 0; j < y; j++){
    
            for (int i = 0; i < x; i++){
    
                b[i] = x - i; // reverse sorted array (even with this assignment taken out still runs slower than python)
    
            }
    
            merge_sort(b, x, temp);
    
        }
    
        cout << "done";
        system("pause");
    }
    


Answer: The core reason is no doubt **timsort** \--
<http://en.wikipedia.org/wiki/Timsort> \-- first conceived by Tim Peters for
Python though now also in some Java VMs (for non-primitives only).

It's a truly amazing algorithm and you can find a C++ implementation at
<https://github.com/swenson/sort> for example.

Lesson to retain: the proper _architecture_ and _algorithms_ can let you run
circles around supposedly-faster _languages_ if the latter are using less-
perfect A & As!-) So, if you have really big problems to solve, deal with
determining perfect architecture and algorithms first -- the language and
optimizations within it are inevitably lower-priority issues.

