深度优先稳定原地归并排序的高效算法

Efficient algorithm of depth-first stable in-place merge sort

基于分治策略,使用深度优先的方法,提出了一种用于线性表的稳定原地归并排序算法,其时间复杂度为O(n lb n),辅助空间复杂度为O(1),递归栈空间复杂度为O(lb n),同时进行了算法分析和实验测试。实验结果表明,该算法效率较STL中的稳定原地归并排序算法有67.51%的提升,解决了稳定排序算法中要么时间复杂度高要么空间复杂度高的问题。

Based on divide-and-conquer strategy,the depth-first method was used to design an algorithm of stable in-place merge sort for linear array.Its time complexity was O（n lb n）,its auxiliary space complexity was O（1）,its space complexity of recursion stack was O（lb n）,and the algorithm analysis and experimental testing were completed.By analyzing the experimental results,its efficiency compared with stable in-place merge sort algorithm in the STL has a 67.51% improvement,which solves the high time complexity or high space complexity problem of stable sorting algorithm.