Breaking the O(n^2) Barrier: Novel Approaches to Time Complexity Analysis in Quick Sort

The most common type of sorting algorithm used is quicksort. As the name suggests it is the one of the most fastest sorting algorithm used since the innovation of sorting. However, this sort has often been criticised for its worst-case time complexity that is O(n^2). Practically the quick sort tends to follow its average case and best-case scenarios most of the time. So practically the quick sort is the most efficient practical sorting algorithm. In this paper we will fine tune this algorithm and remove its worst-case time complexity of O(n^2) and make this the best sorting algorithm both theoretically and practically. Various techniques will be discussed from pivot fixing to randomisation and further using medians of medians.