int sort in C, C++, D

common.c

#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <stdio.h>

#define SIZE (50 * 1000 * 1000)

int data[SIZE];

void init(int* data, int len) {
    int i = 0;
    while (i < len) {
        data[i] = rand();
        i += 1;
    }
}

double t(void) {
    static double t0;
    struct timeval tv;
    gettimeofday(&tv, NULL);
    double h = t0;
    t0 = tv.tv_sec + tv.tv_usec / 1000000.0;
    return t0 - h;
}


void test(int* data, int len) {
    int i = 1;
    while (i < len) {
        if (data[i] < data[i - 1]) {
            printf("*** data not sorted ***\n");
            break;
        }
        i += 1;
    }
}

void common_init(void) {
    //srand(time(NULL));
    srand(0x1337);
    int len = SIZE;
    init(data, len);
}

cpp.cpp

#include <algorithm>
#include <stdio.h>

extern "C" {
    void init(int*, int);
    double t(void);
    void test(int*, int);
    void common_init(void);
}


#define SIZE (50 * 1000 * 1000)
extern int data[SIZE];


void sort(int* data, int len) {
    std::sort(data, data + len);
}

int main() {
    common_init();
    t();
    sort(data, SIZE);
    printf("libc qsort - %d numbers - %.2f s\n", SIZE, t());
    test(data, SIZE);
}

d.d

import core.stdc.stdio;

extern (C) {
    void init(int*, int);
    double t();
    void test(int*, int);
    void common_init();
}


enum SIZE = (50 * 1000 * 1000);
extern(C) __gshared int[SIZE] data;


void sort(int* data, int len) {
    import std.algorithm: sorted = sort;
    sorted(data[0 .. len]);
}

void main() {
    common_init();
    t();
    sort(data.ptr, SIZE);
    printf("libc qsort - %d numbers - %.2f s\n", SIZE, t());
    test(data.ptr, SIZE);
}

manual.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>


void init(int*, int);
double t(void);
void test(int*, int);
void common_init(void);
#define SIZE (50 * 1000 * 1000)
extern int data[SIZE];


void insert_sort(int* left, int* right) {

    // put minimum to left position, so we can save
    // one inner loop comparsion for insert sort
    int min = *left;
    int* pmin = left;
    int* pi = left + 1;
    while (pi <= right) {
        if (*pi < min) {
            pmin = pi;
            min = *pi;
        }
        pi += 1;
    }
    *pmin = *left;
    *left = min;

    pi = left + 2;
    while (pi <= right) {
        int h = *pi;
        int* pj = pi - 1;
        while (h < *pj) {
            *(pj + 1) = *pj;
            pj -= 1;
        }
        *(pj + 1) = h;
        pi += 1;
    }
}

#define swap(a, b) { int _h = a; a = b; b = _h; }

#define sort3fast(a, b, c)                             \
    if (b < a) {                                       \
        if (c < a) {                                   \
            if (c < b) { swap(a, c);}                  \
            else { int h = a; a = b; b = c; c = h;}    \
        }                                              \
        else { swap(a, b); }                           \
    }                                                  \
    else {                                             \
        if (c < b) {                                   \
            if (c < a) { int h = c; c = b; b = a; a = h;} \
            else { swap(b, c); }                       \
        }                                              \
    }                                                  \

int* partition(int* left, int* right) {

    int* left0 = left;
    int pivl = *left;
    left += 1;
    int* p = left0 + (right - left0) / 2;
    int piv = *p;
    *p = *left;
    *left = piv;
    int pivr = *right;

    sort3fast(pivl, piv, pivr);

    *right = pivr;
    *left0 = pivl;
    *left = piv;

    while (1) {
        do left += 1; while(*left < piv);
        do right -= 1; while (*right > piv);
        if (left >= right) break;
        swap(*left, *right);
    }
    *(left0 + 1) = *right;
    *right = piv;
    return right;
}
void sort(int* data, int len) {

    int* stack[64];
    int sp = 0;
    int* left = data;
    int* right = data + len - 1;

    while (1) {
        // for arrays smaller than 50 use insert sort
        if (right - left < 50) {
            insert_sort(left, right);
            if (sp == 0) break;
            sp -= 2;
            left = stack[sp];
            right = stack[sp + 1];
        }
        else {
            int* mid = partition(left, right);
            if (mid < left + (right - left) / 2) {
                stack[sp] = mid + 1;
                stack[sp + 1] = right;
                right = mid - 1;
            }
            else {
                stack[sp] = left;
                stack[sp + 1] = mid - 1;
                left = mid + 1;
            }
            sp += 2;
        }
    }
}


int main(void) {

    common_init();
    t();
    sort(data, SIZE);
    printf("libc qsort - %d numbers - %.2f s\n", SIZE, t());
    test(data, SIZE);
    return 0;
}

manual.cpp

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>


extern "C" {
    void init(int*, int);
    double t(void);
    void test(int*, int);
    void common_init(void);
    #define SIZE (50 * 1000 * 1000)
    extern int data[SIZE];
}

void insert_sort(int* left, int* right) {

    // put minimum to left position, so we can save
    // one inner loop comparsion for insert sort
    int min = *left;
    int* pmin = left;
    int* pi = left + 1;
    while (pi <= right) {
        if (*pi < min) {
            pmin = pi;
            min = *pi;
        }
        pi += 1;
    }
    *pmin = *left;
    *left = min;

    pi = left + 2;
    while (pi <= right) {
        int h = *pi;
        int* pj = pi - 1;
        while (h < *pj) {
            *(pj + 1) = *pj;
            pj -= 1;
        }
        *(pj + 1) = h;
        pi += 1;
    }
}

#define swap(a, b) { int _h = a; a = b; b = _h; }

#define sort3fast(a, b, c)                             \
    if (b < a) {                                       \
        if (c < a) {                                   \
            if (c < b) { swap(a, c);}                  \
            else { int h = a; a = b; b = c; c = h;}    \
        }                                              \
        else { swap(a, b); }                           \
    }                                                  \
    else {                                             \
        if (c < b) {                                   \
            if (c < a) { int h = c; c = b; b = a; a = h;} \
            else { swap(b, c); }                       \
        }                                              \
    }                                                  \

int* partition(int* left, int* right) {

    int* left0 = left;
    int pivl = *left;
    left += 1;
    int* p = left0 + (right - left0) / 2;
    int piv = *p;
    *p = *left;
    *left = piv;
    int pivr = *right;

    sort3fast(pivl, piv, pivr);

    *right = pivr;
    *left0 = pivl;
    *left = piv;

    while (1) {
        do left += 1; while(*left < piv);
        do right -= 1; while (*right > piv);
        if (left >= right) break;
        swap(*left, *right);
    }
    *(left0 + 1) = *right;
    *right = piv;
    return right;
}
void sort(int* data, int len) {

    int* stack[64];
    int sp = 0;
    int* left = data;
    int* right = data + len - 1;

    while (1) {
        // for arrays smaller than 50 use insert sort
        if (right - left < 50) {
            insert_sort(left, right);
            if (sp == 0) break;
            sp -= 2;
            left = stack[sp];
            right = stack[sp + 1];
        }
        else {
            int* mid = partition(left, right);
            if (mid < left + (right - left) / 2) {
                stack[sp] = mid + 1;
                stack[sp + 1] = right;
                right = mid - 1;
            }
            else {
                stack[sp] = left;
                stack[sp + 1] = mid - 1;
                left = mid + 1;
            }
            sp += 2;
        }
    }
}


int main(void) {

    common_init();
    t();
    sort(data, SIZE);
    printf("libc qsort - %d numbers - %.2f s\n", SIZE, t());
    test(data, SIZE);
    return 0;
}

manual.d

import core.stdc.stdio;
import std.algorithm: swap;


extern (C) {
    void init(int*, int);
    double t();
    void test(int*, int);
    void common_init();
}

enum SIZE = (50 * 1000 * 1000);
extern(C) __gshared int[SIZE] data;


void insert_sort(int* left, int* right) {

    // put minimum to left position, so we can save
    // one inner loop comparsion for insert sort
    int min = *left;
    int* pmin = left;
    int* pi = left + 1;
    while (pi <= right) {
        if (*pi < min) {
            pmin = pi;
            min = *pi;
        }
        pi += 1;
    }
    *pmin = *left;
    *left = min;

    pi = left + 2;
    while (pi <= right) {
        int h = *pi;
        int* pj = pi - 1;
        while (h < *pj) {
            *(pj + 1) = *pj;
            pj -= 1;
        }
        *(pj + 1) = h;
        pi += 1;
    }
}


void sort3fast(ref int a, ref int b, ref int c) {
    if (b < a) {
        if (c < a) {
            if (c < b) { swap(a, c);}
            else { int h = a; a = b; b = c; c = h;}
        }
        else { swap(a, b); }
    }
    else {
        if (c < b) {
            if (c < a) { int h = c; c = b; b = a; a = h;}
            else { swap(b, c); }
        }
    }
}

int* partition(int* left, int* right) {

    int* left0 = left;
    int pivl = *left;
    left += 1;
    int* p = left0 + (right - left0) / 2;
    int piv = *p;
    *p = *left;
    *left = piv;
    int pivr = *right;

    sort3fast(pivl, piv, pivr);

    *right = pivr;
    *left0 = pivl;
    *left = piv;

    while (1) {
        do left += 1; while(*left < piv);
        do right -= 1; while (*right > piv);
        if (left >= right) break;
        swap(*left, *right);
    }
    *(left0 + 1) = *right;
    *right = piv;
    return right;
}
void sort(int* data, int len) {

    int*[64] stack;
    int sp = 0;
    int* left = data;
    int* right = data + len - 1;

    while (1) {
        // for arrays smaller than 50 use insert sort
        if (right - left < 50) {
            insert_sort(left, right);
            if (sp == 0) break;
            sp -= 2;
            left = stack[sp];
            right = stack[sp + 1];
        }
        else {
            int* mid = partition(left, right);
            if (mid < left + (right - left) / 2) {
                stack[sp] = mid + 1;
                stack[sp + 1] = right;
                right = mid - 1;
            }
            else {
                stack[sp] = left;
                stack[sp + 1] = mid - 1;
                left = mid + 1;
            }
            sp += 2;
        }
    }
}


void main() {

    common_init();
    t();
    sort(data.ptr, SIZE);
    printf("libc qsort - %d numbers - %.2f s\n", SIZE, t());
    test(data.ptr, SIZE);
}

qsort.c

#include <stdio.h>
#include <stdlib.h>

void init(int*, int);
double t(void);
void test(int*, int);
void common_init(void);
#define SIZE (50 * 1000 * 1000)
extern int data[SIZE];


int cmpfunc (const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

void sort(int* data, int len) {
    qsort(data, len, sizeof(int), cmpfunc);
}


int main(void) {

    common_init();
    t();
    sort(data, SIZE);
    printf("libc qsort - %d numbers - %.2f s\n", SIZE, t());
    test(data, SIZE);
    return 0;
}