"Beating" the linux ...

I am programming parallel sorting algorithms with MPI / C++ on computer clusters right now, and therefore had to implement qsort in a serial fashion (before creating a parallelized version of it) ..

For arrays of integers, the following "pedestrian" C-code implementation beats the builtin quicksort implementation (defined by ISO) on Linux by being 58% percent faster...

inline void swap(int* p1, int* p2) {

    int tmp = *p1;

    *p1 = *p2;

    *p2 = tmp;

}



inline int divide(int* start, int* end, int pivotIndex) {

    int len = end - start + 1;

    int pivot = start[pivotIndex];

    int storeIndex = 0;



    swap(&start[pivotIndex], &start[len-1]);

    for (int i=0; i < len-1; i++) {

        if (start[i] < pivot) {

            swap(&start[i], &start[storeIndex++]);            

        }

    }

    swap(&start[storeIndex], &start[len-1]);



    return storeIndex;

}



inline void mysort(int* start, int* end) {

    int len = end - start + 1;

    if (start >= end || len == 1) {

        return;

    }

    int pivotIndex = rand() % len;

    int newPivotIndex = divide(start, end, pivotIndex);

    mysort(&start[0], &start[newPivotIndex-1]);

    mysort(&start[newPivotIndex+1], end);

}

These are my results for a randomized array of integers...

Sorting 57 MB

My sort: 3694 msec

Quicksort: 5861 msec



Intel(R) Pentium(R) D CPU 3.00GHz (Presler)

2GB RAM

Linux 2.6.32-5-amd64 x86_64 GNU/Linux

g++ (Debian 4.4.5-8) 4.4.5

glibc 2.11.2

Not bad.. The reason? Inlining. . Rather missing inlining. For glibc qsort, the comparison method (which I provide) can't be inlined, since the code for qsort has already been generated, it's in glibc. Again, in my implementation the comparison is within the existing divide method.

The complete file, for those interested: main_sort.cpp. For large arrays, be sure to set the maximum stacksize accordingly.

Again, on Windows the qsort provided by VS 2010 is twice as fast as my implementation!

PS: I know, this ain't real "beating", because it doesn't improve the algorithmic complexity