Quick Sort Optimized for Non-decreasing Data set

The Sorting Algorithm proposed by C.A.R Hoare  in 1961 by name Quick sort,  which is popularly known for being the fastest sorting algorithm. Quick sort  is still being practiced in the field of computers systems and its applications. The Algorithm whose efficiency to sort random data set is represented in asymptotic notation as  O(n log2 n) and when quick sort algorithm has a input data set which is already Ordered then it takes  a quadratic execution time which is considered as a worst case performance and this behavior is represented in asymptotic notation as O(n2). The  worst case performance is due the scan over heads which occur over the pre-sorted data set, in other words the partitioning gets skewed due to recursive calls and hence results in a quadratic complexity. This research paper presents an algorithm  which minimizes a worst case execution time making it linear when the input list is in non-decreasing order. The paper describes how the improvements are accommodated in the existing quick sort. A priori analysis of  proposed algorithm for different cases is made along with a proof of  correctness. Later the algorithm is verified for its correctness and asymptotic performance. The algorithm is implemented using C++ and also we have compared with other popular quick-sort version.