A Comprehensive Note on Complexity Issues in Sorting Algorithms

Since the dawn of computing, the sorting problem has attracted a great deal of research. Inpast, many researchers have attempted to optimize it properly using empirical analysis. We haveinvestigated the complexity values researchers have obtained and observed that there is scope for finetuning in present context. Strong evidence to that effect is also presented. We aim to provide a usefuland comprehensive note to researcher about how complexity aspects of sorting algorithms can be bestanalyzed. It is also intended current researchers to think about whether their own work might beimproved by a suggestive fine tuning. Our work is based on the knowledge learned after literaturereview of experimentation, survey paper analysis being carried out for the performance improvements ofsorting algorithms. Although written from the perspective of a theoretical computer scientist, it isintended to be of use to researchers from all fields who want to study sorting algorithms rigorously.