QUICK SORT
Quick sort,is based on the divide-and-conquer paradigm.It is a sorting algorithm with worst case running time O(n^2) on an input array of n numbers.In spite of this slow worst case running time,quicksort is often the best practical choice for sorting because it is remarkably efficient on the average : its expected running time is O(nlgn) and the constants hidden in the O-notation are quite small.Here is the three-step divide-and-conquer process for sorting a typical array A[p . . . r]
DIVIDE:The array >A is partitioned (rearranged) into two nonempty subarrays A[p . . q] and A[q+1 . . r].The index q is computed as a part of this partitioning procedure.
CONQUER:The two subarrays A[p . . q] and A[q+1 . . r] are sorted by recursive calls to quicksort.
COMBINE:Since the subarrays are sorted in place, no work is needed to combine them : the entire array A is now sorted.
