C标准中的qsort函数，可以对任意类型的数组进行快速排序，用起来也还算方便，不过
行为有一点诡异。加上之前曾经看过
一篇文章（沈大写的，曾经登上过ecom的双周刊，居然在这个youalab.com也等出来了-。-），说是qsort不是线程安全的，所以把glibc的代码翻出来，看看qsort的具体实现。
用Ubuntu的话，找代码就很容易了：
引用
$ apt-get source libc6
$ cd eglibc-xxxx
$ grep -r . -Hne qsort | grep void
可以看到qsort是在stdlib.h里面的，源码在msort.c 302行，调用了qsort_r函数：
void
qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
{
return qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);
}
其中__compar_fn_t就是 int (*)(const void *, const void *)类型的函数指针，__compar_d_fn_t则是 int (*)(const void *, const void *, void *)类型的函数指针(为什么还有个void *呢?很神奇~求解)。
qsort_r函数也在msort.c中，约164行起。为了榨干CPU的性能，写了很多代码来优化效率，其流程大致是：
1. 判断额外所需内存大小，如果很小(<1024B)，在栈上分配；否则获取系统内存参数——如果比可用内存小，试图在堆上分配；如果所需内存超过物理内存（为防出现不得不使用交换分区的情况致使性能恶化，故不分配），或者分配失败（可用空间不足），使用性能较差的stdlib/qsort.c中的_quicksort函数来排序。
1.1. _quicksort位于 stdlib/qsort.c，对快排进行了两个改进：1. 将递归转化为递推; 2. 使用插入排序来处理4个元素以内的区间。不过用于交换两个元素的宏SWAP(a, b, size)没有额外的优化，比较意外（本来以为会考虑一次多个字节拷贝，或者使用duff device来减少循环）。
2. 分配成功的情况下，使用额外分配的空间，调用 msort_with_tmp() 函数来进行排序。
2.1. 如果单个元素的大小超过32个字节，那么使用间接排序，分配空间时就有额外的判断，如果需要间接排序，则额外分配2n个指针的空间，前n个空间用于存放原指针，后n个空间用于按照所指元素大小存放排序好的指针。最后再按照排序好的指针顺序将元素拷贝。(注释中提到了Knuth vol. 3 (2nd ed.) exercise 5.2-10.，应该是指这个算法出自Knuth的《The Art of Computer Programming》卷3吧)
2.2. 否则使用直接排序。这里也进行了一些优化，主要是为msort_with_tmp()提供p.var参数，完成针对元素的大小进行拷贝的优化：默认是使用gcc内置的__builtin_mempcpy来拷贝。
2.3. msort_with_tmp对典型的快排也进行了非常赞的优化。
2.3.1. 从msort_with_tmp的函数名和代码可以看出，这个算法不是就地排序，而是使用了第一步分配的O(N)的额外空间，这样可以让排序时的拷贝效率更高（这个优化应该对CPU的cache命中率也有较大的提高）。
2.3.2. qsort_r传进来的参数p有个属性var
(1) 默认情况下p.var = 4，使用mempcpy来进行拷贝。
(2) 如果单个元素大于32bytes，p.var = 3, 表示是间接排序，拷贝的是指针，不是元素
(3) 如果数组是按uint32_t对其的，且元素的大小是uint32_t的倍数，则可以进一步优化到每次按照uint32_t/uint64_t/unsigned long来进行拷贝，一次拷贝4或者8个字节，此时p.var = 0,1,2表示按照uint32_t, uint64_t, unsigned long拷贝。
直接在里头做了些注释，有兴趣的话可以更仔细地看看。可以的话自己去下了glibc的源码阅读，更有意思:D
