快速排序最差情況下的時間複雜度？

Question

我正在研究一個項目，該項目改進了快速排序算法的最壞情況時間複雜度。我通過選擇中位數而不是最左邊的選擇來修改算法，並且在一定數量的迭代之後引入插入排序。結果如下：

對於長度爲5000的未排序的數據的〜100000的輸入：

1. 改性快速排序在我作出比較的數目比比較在定期取得的數目非常少快速排序。
2. 如果數據全部長度都爲零，則兩者的運行時間爲零秒。

對於長度爲5000的已排序的數據，以100000的輸入：

1. 我修改快速排序作出比較的數量仍比比較常規單觸發的數量非常少的分類。
2. 我修改過的快速排序所用的時間比所有數據長度的常規快速排序所耗用的時間少得多。

我該如何證明已經排序的數據的時間複雜度爲O(n^2)已得到改進？我有上述所有數據，但不知道如何理論上顯示它？沒有直接的答案，但提示將罰款。

Answer 1

演示算法改進排序算法的常用方法是測試代碼來計算比較次數，然後在幾個不同的數據集上運行不同的算法，每個數據集都有不同的特徵（隨機，已排序，反向排序，等）。

一個好的模型對這種分析的是蒂姆·彼得寫了他的Timsort算法：http://hg.python.org/cpython/file/2.7/Objects/listsort.txt