Samplesort：最小存储树排序的采样方法

目前使用的和之前提出的选择最小存储树排序根节点的方法实际上是对待排序序列中位数进行低效统计估计的方法。通过有效利用在输入待排序序列时选择的随机样本中的信息，可以显著改进普通最小存储树排序。提出了一种程序，它是最小存储树排序的推广，并具有以下三个特性：(a) 排序输入序列所需的比较次数在期望值上显著减少（相比普通最小存储树排序）。(b) 该程序对输入序列中的偏差在统计上不敏感。(c) 该程序所需的比较次数的期望值逐渐接近信息论上比较次数的下界。因此，该程序是“渐近最优”的.