c - イントロソート - 反復バリアントが遅くなる

Question

ちょっとした楽しみとして、私は Introsort の反復バリアントを実装しようとしています。デフォルトの実装は次のようになります。

void introsort_loop(int *a, size_t left, size_t right, size_t threshold, size_t depth) {

    while(right-left > threshold) {

        if(depth == 0) {
            heapsort(a, left, right);
            return;
        }

        --depth;

        int p = partition(a, left, right);

        introsort_loop(p, right, depth);
        right = p-1;
    }
}

void introsort(int *array, size_t num, size_t threshold) {  

    if(num > 1) {   
        introsort_loop(a, 0, num-1, threshold, log2(num)*2);
        insertionsort(a, num);
    }
}

たまたま反復クイックソートを実装しているため、反復イントロソートの基礎としてのglibc実装を使用しています。qsortqsort

私の実装は次のようになります。

#include <limits.h>
#include <math.h>
#include "introsort.h"

// Stack node declarations used to store unfulfilled partition obligations.
typedef struct {
    int lo;
    int hi;
} stack_node;

// The next 4 #defines implement a very fast in-line stack abstraction.
// The stack needs log (total_elements) entries (we could even subtract
// log(threshold)).  Since num has type size_t, we get as
// upper bound for log (num):
// bits per byte (CHAR_BIT) * sizeof(size_t).
#define STACK_SIZE (CHAR_BIT*sizeof(size_t))
#define PUSH(low, high) ((top->lo = (low)), (top->hi = (high)), ++top)
#define POP(low, high) (--top, ((low) = top->lo), ((high) = top->hi))
#define STACK_NOT_EMPTY (stack < top)

#define SWAP(a, i, j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; }
#define PARENT(i)       ((i-1)/2)
#define LEFT_CHILD(i)   (((i)<<1)+1)

void heapify_i(int *a, int left, int right) {

    int child, swap;
    int root = left;

    while((child = LEFT_CHILD(root)) <= right) {
        swap = root;
        if(a[swap] < a[child]) {
            swap = child;
        }

        if(child+1 <= right && a[swap] < a[child+1]) {
            swap = child+1;
        }

        if(swap == root) {
            break;
        } else {
            SWAP(a, root, swap);
            root = swap;
        }
    }
}

void heapsort_i(int *a, int left, int right) {

    int start = left;
    int end = right;

    for(start = PARENT(end); start >= left; --start) {
        heapify_i(a, start, end);
    }

    start = left;
    while(start < end) {
        SWAP(a, start, end);
        heapify_i(a, start, --end);
    }
}

void quicksort_i(int *a, size_t num, size_t threshold, size_t depth) {

    //========== QUICKSORT ==========//
    if(num > threshold) {
        stack_node stack[STACK_SIZE];
        stack_node *top = stack;

        PUSH(-1, -1);

        int low = 0;
        int high = num-1;
        int left, mid, right;

        while(STACK_NOT_EMPTY) {

            if(depth == 0) {
                heapsort_i(a, low, high);
                break;
            } else {
                --depth;

                //========== PIVOT = MID (MEDIAN OF THREE) ==========
                mid = low+(high-low)/2;

                if(a[mid] < a[low]) {
                    SWAP(a, mid, low);
                }

                if(a[high] < a[mid]) {
                    SWAP(a, high, mid);
                } else {
                    goto jump_qi;
                }

                if(a[mid] < a[low]) {
                    SWAP(a, mid, low);
                }
                jump_qi:;

                //========== PARTITIONING ==========//
                left = low+1;
                right = high-1;

                while(left < right) {

                    while(a[left] < a[mid]) {
                        ++left;
                    }

                    while(a[mid] < a[right]) {
                        --right;
                    }

                    if(left < right) {
                        SWAP(a, left, right);

                        if(mid == left) {
                            mid = right;
                        } else if(mid == right) {
                            mid = left;
                        }

                        ++left;
                        --right;
                    }
                }

                // Set up pointers for next iteration.  First determine whether
                // left and right partitions are below the threshold size.  If so,
                // ignore one or both.  Otherwise, push the larger partition's
                // bounds on the stack and continue sorting the smaller one.
                if(right-low < threshold) {

                    if(high-left <= threshold) {
                        // ignore both small partitions
                        POP(low, high);
                    } else {
                        // ignore small left partition
                        low = left;
                    }

                } else if(high-left <= threshold) {
                    // ignore small right partition
                    high = right;
                } else if(right-low > high-left) {
                    // push larger left partition
                    PUSH(low, right);
                    low = left;
                } else {
                    // push larger right partition
                    PUSH(left, high);
                    high = right;
                }
            }
        }
    }

    //========== INSERTION SORT ==========//
    int e, i, j;

    for(i = 1; i <= num; ++i) {

        e = a[i];
        for(j = i-1; j >= 0 && e < a[j]; --j) {
            a[j+1] = a[j];
        }
        a[j+1] = e;
    }
}

void introsort_i(int *array, size_t num, size_t threshold) {

    if(num > 1) {
        quicksort_i(array, num-1, threshold, log2(num)*2);
    }
}

10ランダムな要素へのサイズの入力では100'000問題なく動作するように見えますが、100 万の要素をテストすると、突然数秒まで遅くなり、100 万の要素を持つ単一の配列には長すぎます。

これを修正するにはどうすればよいですか?