#
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.