PROBABILISTIC ANALYSIS OF THE TIME-COMPLEXITY OF QUICKSORT

Quicksort is a well-known sorting algorithm based on the divided contr ol. The array to be sorted is divided into two sets as follows. An ele ment in the array is specified, and the set of values larger than the value of that element and the set of values smaller than that value ar e constructed. Each of those two sets are sorted independently. The pr ocedure is iterated for the divided sets. In other words, the algorith m has a recursive structure. The average time-complexity of the quicks ort (the average number of comparisons) is O(n log n). Depending on th e data to be sorted, however, the performance may be: deteriorated dra stically. In the worst case, the time complexity is O(n(2)).