Quick-sort Worst case time complexity?

1
votes

I am working on a Project that improves the Quick-sort algorithms worst case time complexity. I modified the algorithm by choosing the median pivot instead of the left most selection and introduced insertion sort after a certain number of iterations. The results are as follows:

For an input of unsorted data of length 5000 to 100000:

  1. The number of Comparison made in my modified Quick-sort are very less than the number of comparisons made in regular Quick-sort.
  2. Elapsed time for both is zero secs for all length if data.

For an input of already sorted data of length 5000 to 100000:

  1. The number of Comparison made in my modified Quick-sort are still very less than the number of comparisons made in regular Quick-sort.
  2. Elapsed time for my modified Quick-sort is very less than the elapsed time of the regular Quick-sort for all length of data.

How can I now prove that the time complexity O(n^2) for already sorted data has been improved? I have all the above data but dont know how to theoretically show it? No direct answers but hints will be fine.

1
algorithmquicksort
A little secret. "your" improvement has already been discovered so many years ago. - Aurelio De Rosa
I know. But I had to implement it on my own instead of just copying the concepts from somewhere. - user1031752
@AurelioDeRosa I believe Robert Sedgewick's career got launched with these improvements. See "The Analysis of Quicksort Programs, " Acta Informatica 7, 1977. - Raymond Hettinger
@RaymondHettinger Good for the reference ;) - Aurelio De Rosa
You will have to use probability theory and do some math. There is no other way. Counting comparisons might suggest some trends, but its certainly not a proof. - malejpavouk

1 Answers

2
votes

The usual way to demonstrate algorithmic improvements in sorting algorithms is to instrument the code to count the number of comparisons and then run different algorithms over several different datasets, each with different characteristics (random, already sorted, reverse sorted, mostly sorted, etc).

A good model for this kind of analysis is Tim Peter's write-up for his Timsort algorithm: http://hg.python.org/cpython/file/2.7/Objects/listsort.txt