algorithm - 快速排序最坏情况时间复杂度？

Question

我正在从事一个改进快速排序算法最坏情况时间复杂度的项目。我通过选择中值主元而不是最左边的选择来修改算法，并在一定次数的迭代后引入插入排序。结果如下:

对于长度为 5000 到 100000 的未排序数据的输入:

1. 我修改后的快速排序中进行的比较次数比常规快速排序中进行的比较次数少得多。
2. 对于所有长度的数据，两者的运行时间均为零秒。

对于长度为 5000 到 100000 的已排序数据的输入:

1. 在我修改后的快速排序中进行的比较次数仍然远远少于在常规快速排序中进行的比较次数。
2. 对于所有长度的数据，我修改后的快速排序所用的时间比常规快速排序所用的时间少得多。

我现在如何证明已排序数据的时间复杂度 O(n^2) 得到了改进？我有以上所有数据，但不知道理论上如何显示？没有直接的答案，但提示就可以了。

Answer 1

展示排序算法中算法改进的常用方法是检测代码以计算比较次数，然后在几个不同的数据集上运行不同的算法，每个数据集具有不同的特征(随机、已排序、反向排序、大部分已排序、等)。

Tim Peter 为他的 Timsort 撰写的文章是此类分析的一个很好的模型。算法:http://hg.python.org/cpython/file/2.7/Objects/listsort.txt