static void quickSortHelper()

in source/sigv4_quicksort.c [125:198]

• 44 lines of code
• 9 McCabe index (conditional complexity)

static void quickSortHelper( void * pArray,
                             size_t low,
                             size_t high,
                             size_t itemSize,
                             ComparisonFunc_t comparator )
{
    size_t stack[ SIGV4_WORST_CASE_SORT_STACK_SIZE ];

    /* Low and high are first two items on the stack. Note
     * that we use an intermediary variable for MISRA compliance. */
    size_t top = 0U, lo = low, hi = high;

    PUSH_STACK( lo, stack, top );
    PUSH_STACK( hi, stack, top );

    while( top > 0U )
    {
        size_t partitionIndex;
        size_t len1, len2;
        POP_STACK( hi, stack, top );
        POP_STACK( lo, stack, top );

        partitionIndex = partition( pArray, lo, hi, itemSize, comparator );

        /* Calculate length of the left partition containing items smaller
         * than the pivot element.
         * The length is zero if either:
         * 1. The pivoted item is the smallest in the the array before partitioning.
         *              OR
         * 2. The left partition is only of single length which can be treated as
         * sorted, and thus, of zero length for avoided adding to the stack. */
        len1 = ( ( partitionIndex != 0U ) && ( ( partitionIndex - 1U ) > lo ) ) ? ( partitionIndex - lo ) : 0U;

        /* Calculate length of the right partition containing items greater than
         * or equal to the pivot item.
         * The calculated length is zero if either:
         * 1. The pivoted item is the greatest in the the array before partitioning.
         *              OR
         * 2. The right partition contains only a single length which can be treated as
         * sorted, and thereby, of zero length to avoid adding to the stack. */
        len2 = ( ( partitionIndex + 1U ) < hi ) ? ( hi - partitionIndex ) : 0U;

        /* Push the information of the left and right partitions to the stack.
         * Note: For stack space optimization, the larger of the partitions is pushed
         * first and the smaller is pushed later so that the smaller part of the tree
         * is completed first without increasing stack space usage before coming back
         * to the larger partition. */
        if( len1 > len2 )
        {
            PUSH_STACK( lo, stack, top );
            PUSH_STACK( partitionIndex - 1U, stack, top );

            if( len2 > 0U )
            {
                PUSH_STACK( partitionIndex + 1U, stack, top );
                PUSH_STACK( hi, stack, top );
            }
        }
        else
        {
            if( len2 > 0U )
            {
                PUSH_STACK( partitionIndex + 1U, stack, top );
                PUSH_STACK( hi, stack, top );
            }

            if( len1 > 0U )
            {
                PUSH_STACK( lo, stack, top );
                PUSH_STACK( partitionIndex - 1U, stack, top );
            }
        }
    }
}