在什么情况下堆排序比不稳定的就地合并排序更好？

Question

我进行了不稳定的就地合并排序（不分成两部分并照常合并），比std::__partial_sort（当std::sort放弃quicksort时的堆排序）快2到3倍。

因此，在任何情况下，堆排序在任何情况下都比不稳定的就地合并排序更好？当递归太深时，为什么在std::sort中使用堆排序？

P.S。还有什么其他小事情可以用来优化此代码？

#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
template<class T> void auxMerge(T* x, T* y, T* e, T* v){
    for (T *p=v, *q=x; q!=y; ++p, ++q) {
        std::swap (*p, *q);
    }
    for (T *t=v, *d=x, *s=y; d!=s; ++d) {
        if (s==e) {
            do std::swap(*t++,*d++); while (d!=s); return;
        }
        std::swap (*(*s<*t ? s++ : t++), *d);
    }
};
template<class T> void auxSort(T* x, int n, T* t){
    const int Q = 1;
    if (n<=Q) {
        //std::sort (x, x+n);
    } else {
        auxSort(x, n/2, t);
        auxSort(x+n/2, n-(n/2), t);
        auxMerge(x, x+n/2, x+n, t);
    }
};
template<class T> void inplace_mergesort(T* arr, int n) {
    const int Q = 1;
    int fx = (n+2)/3;
    auxSort(arr+fx, n-fx, arr);
    while (fx > Q) {
        int fy = (fx+1)/2;
        auxSort(arr+fy, fx-fy, arr);
        auxMerge(arr+fy, arr+fx, arr+n, arr);
        fx = fy;
    }
    T tmp[Q];
    //std::sort(arr, arr+fx);
    auxMerge(arr, arr+fx, arr+n, tmp);
}
const int N=1<<24;
int A[N];
int main() {
    srand(time(0));
    for (int i=0; i<N; ++i) A[i]=i;
    for (int K=0; K<10; ++K) {
        for (int i=N; i--; ) std::swap(A[i], A[(rand()<<15|rand())%(i+1)]); // My rand() return [0,32767]
        time_t ta = clock();
        inplace_mergesort(A, N);
        printf ("%d\n", clock()-ta);
        for (int i=0; i<N; ++i) if (A[i]!=i) return printf("[%d]=%d\n", i, A[i]);
    }
}

Answer 1

在哪种情况下堆排序比不稳定的就地合并排序更好？

一种内存受限的情况，其中无法提供mege类别的辅助存储。堆排序使用常量存储。