Sorting routines for C99 (with testbed in C++11)

sort.cpp

#include <memory>
#include <iostream>
#include <algorithm>
#include <climits>

#define SWAP(T, x, y) \
        { \
            T z = x; \
            (x) = y; \
            (y) = z; \
        }
#define CMP_SWAP(T, x, y) if ((x) > (y)) SWAP(T, x, y)

#define DECLARE_INSERTION_SORT(name, T, is_less_than) \
    static inline void insertion_sort_##name(T* p, size_t n) { \
        for (size_t i = 1; i < n; ++i) { \
            T e = p[i]; \
            size_t j = i; \
            for (; j > 0 && is_less_than(&e, &p[j - 1]); --j) \
                p[j] = p[j - 1]; \
            p[j] = e; \
        } \
    }

#define DECLARE_SHELL_SORT(name, T, is_less_than) \
    static inline void shell_sort_##name(T* p, size_t n) { \
        size_t gaps[] = { 701, 301, 132, 57, 23, 10, 4, 1 }; \
        for (size_t k = 0; k < sizeof(gaps) / sizeof(gaps[0]); ++k) { \
            size_t gap = gaps[k]; \
            for (size_t i = gap; i < n; ++i) { \
                T e = p[i]; \
                size_t j = i; \
                for (; j >= gap && is_less_than(&e, &p[j - gap]); j -= gap) \
                    p[j] = p[j - gap]; \
                p[j] = e; \
            } \
        } \
    }

#define DECLARE_PARTITION(name, T, data, predicate) \
    static inline size_t partition_##name(T* p, size_t n, data predicate_data) { \
        size_t i = 0; \
        while (i < n && predicate(&p[i], predicate_data)) i++; \
        size_t j = i; \
        for (; i < n; ++i) { \
            if (predicate(&p[i], predicate_data)) { \
                T e = p[i]; \
                p[i] = p[j]; \
                p[j] = e; \
                j++; \
            } \
        } \
        return j; \
    }

#define DECLARE_QUICK_SORT(name, T, is_less_than) \
    static inline bool name##_is_not_greater_than(const T* a, const T* b) { return !is_less_than(b, a); } \
    DECLARE_INSERTION_SORT(name##_is_less_than, T, is_less_than) \
    DECLARE_PARTITION(name##_is_less_than, T, const T*, is_less_than) \
    DECLARE_PARTITION(name##_is_not_greater_than, T, const T*, name##_is_not_greater_than) \
    static void quick_sort_##name(T* p, size_t n) { \
        if (n < 64) { \
            /* Switch to insertion sort for small arrays */ \
            insertion_sort_##name##_is_less_than(p, n); \
        } else { \
            T a = p[0]; \
            T b = p[n / 2]; \
            T c = p[n - 1]; \
            CMP_SWAP(T, a, b) \
            CMP_SWAP(T, b, c) \
            CMP_SWAP(T, a, c) \
            /* Put the median in the last element */ \
            p[0    ] = a; \
            p[n / 2] = b; \
            p[n - 1] = c; \
            /* Split the array in 3 parts: < b, == b, > b */ \
            size_t i = partition_##name##_is_less_than(p, n, &b); \
            size_t k = partition_##name##_is_not_greater_than(p + i, n - i, &b) + i; \
            /* Sort the two parts: < b and > b, processing the smallest first */ \
            if (i < n - k) { \
                quick_sort_##name(p, i); \
                quick_sort_##name(p + k, n - k); \
            } else { \
                quick_sort_##name(p + k, n - k); \
                quick_sort_##name(p, i); \
            } \
        } \
    }

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

static inline bool is_less_than(const int* a, const int* b) { return *a < *b; }
DECLARE_QUICK_SORT(ints, int, is_less_than)
DECLARE_SHELL_SORT(ints, int, is_less_than)

int main() {
    size_t n = 100000, m = 1000;
    std::unique_ptr<int[]> a(new int[n]);
    size_t sum = 0;
    for (size_t j = 0; j < m; ++j) {
        size_t h = 0;
        for (size_t i = 0; i < n; ++i) {
            h = (h * 33) + i;
            a[i] = h % n;
        }
        //std::sort(a.get(), a.get() + n);
        //quick_sort_ints(a.get(), n);
        shell_sort_ints(a.get(), n);
        //qsort(a.get(), n, sizeof(int), cmp);
        sum += a[n/2];
    }
    if (std::is_sorted(a.get(), a.get() + n))
        std::cout << "OK!" << std::endl;
    else
        std::cout << "BAD" << std::endl;
    /*for (size_t i = 0; i < n; ++i)
        std::cout << a[i] << " ";
    std::cout << std::endl;*/
    return int(sum);
}