一种基于数据分块的快速原地归并算法

与其它排序算法相比，二路归并最适合于对两个有序予表进行排序。归并长度分别为m和n的两个有序予表，经典算法有两种。第一种算法完成归并需要о(m+n)的附加空间，о(m+n)次比较和移动。第二种算法是原地的，但完成归并需要о(m+n)次比较和о(m×n)次移动。经过长期研究，提出了一种基于数据分块的快速原地归并算法。新算法通过将数据分块、对数据块排序等方法最多用о((m+n)log2√m+n次比较和о((m+n)^3/2)次移动完成两个有序予表的原地归并。实验证明，该算法与经典的原地算法相比，极大地降低了元素