Sort macro for C

sort.h

/*
sort.h - v1.0 - High quality quicksort implementation as a macro for C/C++

Implements the algorithm from the paper "Engineering a Sort Function" by
Jon L Bentley and M Douglas McIlroy (1993). 
http://cs.fit.edu/~pkc/classes/writing/samples/bentley93engineering.pdf

The code has been written to be iterative (with a manual data stack) instead 
of recursive like the implementation in the paper. When run through a large 
set of tests with different initial data organization, it seems to be on about 
the same level as std::sort. Compared to C standard library qsort, this 
implementation has significantly better performance, due to inlining of the 
compare function. I am not an expert in sorting though, so tests might be 
faulty. In any case, it works well for my use cases and has a tiny code 
footprint, so I'm happy with it. 

    /Mattias Gustavsson
*/

#ifndef sort_h
#define sort_h

#include <stddef.h>

#ifdef __cplusplus
    #if defined(_MSC_VER)
        #pragma warning( push )        
        #pragma warning( disable: 4577 ) // 'noexcept' used with no exception handling mode specified
    #endif
    #include <type_traits>
    #if defined(_MSC_VER)
        #pragma warning( pop )
    #endif
    #define INTERNAL_SORT_TYPE_OF( A ) std::remove_reference< decltype(A) >::type

    template<typename T> struct internal_sort_trivially_copyable_check { 
        static_assert(std::is_trivially_copyable<T>::value, "sort element type must be trivially copyable");
        enum { value = 1 };
    };
    #define INTERNAL_SORT_COMPATIBLE_TYPE(x) \
        ( (void)sizeof( internal_sort_trivially_copyable_check< typename std::remove_cv< typename std::remove_reference<decltype(x)>::type >::type > ) )
#else
    // msvc supports __typeof__ since v17.9
    #define INTERNAL_SORT_TYPE_OF( A ) __typeof__(A)
    #define INTERNAL_SORT_COMPATIBLE_TYPE( x ) ( (void) 0 )
#endif


#define SORT_EX( ARRAY, COUNT, COMPARE, SWAP ) \
    do { \
        INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__arr = (ARRAY); \
        INTERNAL_SORT_COMPATIBLE_TYPE( *(SORT__arr) ); \
        INTERNAL_SORT_TYPE_OF(COUNT) SORT__n = (COUNT); \
        if( SORT__n > 1 ) { \
            struct { size_t start; size_t count; } SORT__stack[ 64 ]; \
            ptrdiff_t SORT__top = 0; \
            SORT__stack[ SORT__top ].start = 0; \
            SORT__stack[ SORT__top ].count = (size_t)SORT__n; \
            while( SORT__top >= 0 ) { \
                INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__a = SORT__arr + SORT__stack[ SORT__top ].start; \
                size_t SORT__count = SORT__stack[ SORT__top-- ].count; \
                for( ;; ) { \
                    if( SORT__count < 24 ) { \
                        if( SORT__count > 1 ) { \
                            INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__end = SORT__a + SORT__count; \
                            INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__minp = SORT__a; \
                            for( INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__p = SORT__a + 1; SORT__p < SORT__end; ++SORT__p ) \
                                if( COMPARE( SORT__p, SORT__minp ) < 0 ) SORT__minp = SORT__p; \
                                    { SWAP( SORT__a, SORT__minp ); } \
                            for( INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__pm = SORT__a + 1; SORT__pm < SORT__end; ++SORT__pm ) { \
                                INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__pl = SORT__pm; \
                                while( COMPARE( SORT__pl - 1, SORT__pl ) > 0 ) \
                                    { SWAP( SORT__pl, SORT__pl - 1 ); --SORT__pl; } \
                            } \
                        } \
                        break; \
                    } \
                    INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__pm = SORT__a + SORT__count / 2; \
                    if( SORT__count > 40 ) { \
                        INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__pl = SORT__a; \
                        INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__pn = SORT__a + SORT__count - 1; \
                        size_t SORT__s = SORT__count / 8; \
                        { INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__x = SORT__pl, *SORT__y = SORT__pl + SORT__s, *SORT__z = SORT__pl + 2 * SORT__s; \
                          SORT__pl = ( COMPARE( SORT__x,SORT__y ) < 0 ? ( COMPARE( SORT__y,SORT__z ) < 0 ? SORT__y : ( COMPARE( SORT__x,SORT__z ) < 0 ? SORT__z : SORT__x ) ) \
                                                   : ( COMPARE( SORT__y,SORT__z ) > 0 ? SORT__y : ( COMPARE( SORT__x,SORT__z ) > 0 ? SORT__z : SORT__x ) ) ); } \
                        { INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__x = SORT__pm - SORT__s, *SORT__y = SORT__pm, *SORT__z = SORT__pm + SORT__s; \
                          SORT__pm = ( COMPARE( SORT__x,SORT__y ) < 0 ? ( COMPARE( SORT__y,SORT__z ) < 0 ? SORT__y : ( COMPARE( SORT__x,SORT__z ) < 0 ? SORT__z : SORT__x ) ) \
                                                   : ( COMPARE( SORT__y,SORT__z ) > 0 ? SORT__y : ( COMPARE( SORT__x,SORT__z ) > 0 ? SORT__z : SORT__x ) ) ); } \
                        { INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__x = SORT__pn - 2 * SORT__s, *SORT__y = SORT__pn - SORT__s, *SORT__z = SORT__pn; \
                          SORT__pn = ( COMPARE( SORT__x,SORT__y ) < 0 ? ( COMPARE( SORT__y,SORT__z ) < 0 ? SORT__y : ( COMPARE( SORT__x,SORT__z ) < 0 ? SORT__z : SORT__x ) ) \
                                                   : ( COMPARE( SORT__y,SORT__z ) > 0 ? SORT__y : ( COMPARE( SORT__x,SORT__z ) > 0 ? SORT__z : SORT__x ) ) ); } \
                        { INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__x = SORT__pl, *SORT__y = SORT__pm, *SORT__z = SORT__pn; \
                          SORT__pm = ( COMPARE( SORT__x,SORT__y ) < 0 ? ( COMPARE( SORT__y,SORT__z ) < 0 ? SORT__y : ( COMPARE( SORT__x,SORT__z ) < 0 ? SORT__z : SORT__x ) ) \
                                                   : ( COMPARE( SORT__y,SORT__z ) > 0 ? SORT__y : ( COMPARE( SORT__x,SORT__z ) > 0 ? SORT__z : SORT__x ) ) ); } \
                    } \
                    INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__pv = SORT__a; { SWAP( SORT__pv, SORT__pm ); } \
                    INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__pa = SORT__a; \
                    INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__pb = SORT__a; \
                    INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__pc = SORT__a + SORT__count - 1; \
                    INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__pd = SORT__pc; \
                    for( ;; ) { \
                        int SORT__r; \
                        while( SORT__pb <= SORT__pc && ( SORT__r = COMPARE( SORT__pb, SORT__pv ) ) <= 0 ) { \
                            if( SORT__r == 0 ) { SWAP( SORT__pa, SORT__pb ); ++SORT__pa; } \
                            ++SORT__pb; \
                        } \
                        while( SORT__pc >= SORT__pb && ( SORT__r = COMPARE( SORT__pc, SORT__pv ) ) >= 0 ) { \
                            if( SORT__r == 0 ) { SWAP( SORT__pc, SORT__pd ); --SORT__pd; } \
                            --SORT__pc; \
                        } \
                        if( SORT__pb > SORT__pc ) break; \
                        { SWAP( SORT__pb, SORT__pc ); } \
                        ++SORT__pb; --SORT__pc; \
                    } \
                    INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__pn = SORT__a + SORT__count; \
                    ptrdiff_t SORT__s1 = ( ( SORT__pa - SORT__a ) < ( SORT__pb - SORT__pa ) ? ( SORT__pa - SORT__a ) : ( SORT__pb - SORT__pa ) ); \
                    { ptrdiff_t SORT__sn = SORT__s1; INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__sa = SORT__a; INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__sb = SORT__pb - SORT__s1; \
                    while( SORT__sn-- > 0 ) { SWAP( SORT__sa, SORT__sb ); ++SORT__sa; ++SORT__sb; } } \
                    ptrdiff_t SORT__s2 = ( ( SORT__pd - SORT__pc ) < ( SORT__pn - SORT__pd - 1 ) ? ( SORT__pd - SORT__pc ) : ( SORT__pn - SORT__pd - 1 ) ); \
                    { ptrdiff_t SORT__sn = SORT__s2; INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__sa = SORT__pb; INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__sb = SORT__pn - SORT__s2; \
                    while( SORT__sn-- > 0 ) { SWAP( SORT__sa, SORT__sb ); ++SORT__sa; ++SORT__sb; } } \
                    ptrdiff_t SORT__left = ( SORT__pb - SORT__pa ); \
                    ptrdiff_t SORT__right = ( SORT__pd - SORT__pc ); \
                    INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__left_a = SORT__a; \
                    INTERNAL_SORT_TYPE_OF( *(ARRAY) )* SORT__right_a = SORT__pn - SORT__right; \
                    if( SORT__left > 1 && SORT__right > 1 ) { \
                        if( SORT__left > SORT__right ) { \
                            ++SORT__top; SORT__stack[ SORT__top ].start = (size_t)( SORT__left_a - SORT__arr ); \
                            SORT__stack[ SORT__top ].count = (size_t)SORT__left; \
                            SORT__a = SORT__right_a; SORT__count = (size_t)SORT__right; \
                        } else { \
                            ++SORT__top; SORT__stack[ SORT__top ].start = (size_t)( SORT__right_a - SORT__arr ); \
                            SORT__stack[ SORT__top ].count = (size_t)SORT__right; \
                            SORT__a = SORT__left_a; SORT__count = (size_t)SORT__left; \
                        } \
                        continue; \
                    } else if( SORT__left > 1 ) { SORT__a = SORT__left_a; SORT__count = (size_t)SORT__left; continue; } \
                    else if( SORT__right > 1 ) { SORT__a = SORT__right_a; SORT__count = (size_t)SORT__right; continue; } \
                    else { break; } \
                } \
            } \
        } \
    } while( 0 )


#define SORT_DEFAULT_SWAP( PA, PB ) \
    do { \
        INTERNAL_SORT_TYPE_OF( (PA) ) SORT__swap_a = (PA); \
        INTERNAL_SORT_TYPE_OF( (PB) ) SORT__swap_b = (PB); \
        INTERNAL_SORT_TYPE_OF( *SORT__swap_a ) SORT__t = *SORT__swap_a; \
        *SORT__swap_a = *SORT__swap_b; \
        *SORT__swap_b = SORT__t; \
    } while( 0 )


#define SORT( ARRAY, COUNT, COMPARE ) \
    SORT_EX( ARRAY, COUNT, COMPARE, SORT_DEFAULT_SWAP )

#endif // sort_h