ADMISSION NOTICE (2024-2025) New   Notification of Appointment as Assistant Professors New   NPTEL ENROLLMENT DETAILS AND LIST OF COURSES ( JULY- DEC 2024) New   NAAC REACCREDITED WITH A++ CGPA OF 3.51 New   New Programmes started in PWC 2024 New    Patna Women’s College gets remarkable ranking in MDRA – India Today Best Colleges 2023 New  Corona Crusaders College Magazine New   Alumni Association Life Membership/Contribution Form Link New   Patna Women's College is ranked at a rank band of 101 - 150 in the NIRF 2021 Ranking under College category

Enter your keyword

A Comparative Analysis of Sorting Algorithms under Discrete Uniform Distribution

Explore –Journal of Research

                                    Peer Reviewed Journal

     ISSN 2278–0297 (Print)

                                                                                                ISSN 2278–6414 (Online)

                Vol. XIV No. 2, 2022

© Patna Women’s College, Patna, India


A Comparative Analysis of Sorting Algorithms under Discrete Uniform Distribution


Received                                   : April 2022

Accepted                                   : May 2022

Corresponding Author   : Priyadarshini

Abstract : Sorting can be viewed as one of the fundamental aspects of computer applications. The efficiency of a sorting algorithm is a major issue when the amount of data to be sorted is large. Different sorting algorithms are analyzed based on time complexity and space complexity to select the efficient one based on their execution time for varying input sizes. In the case of sorting algorithms, when the array elements to be sorted are randomly generated from some probability distribution; then the true ability of an algorithm can be judged only when it is supported by the study of parametric complexity analysis which includes the study of the behaviour of running times as a function of parameters of the input distribution. To select a particular sorting algorithm from among a set of several algorithms, the behaviour of the parameters of the input distribution plays an important role and it can’t be ignored as far as the efficiency of the algorithm is concerned. In this paper, discrete uniform distribution is chosen for the study.

Three sorting algorithms, having similar average-case complexity O (N log N), quick sort, heap sort and merge sort have been chosen here for statistical comparative study of their parametric complexity. The purpose of the study is to investigate the effect of the parameter of the discrete uniform distribution on the sorting time of the three sorting algorithms under study. While working with several algorithms, one way to judge the best algorithm is to find the execution time T(n), as a function of N(input size) and examine the run time complexity using big O notation. However, sometimes it is difficult to find the exact form of the function and it becomes difficult to predict the complexity/ efficiency of an algorithm. Further, it has been tried to find the best sorting algorithm by performing a variance-based analysis of the sorting algorithms.

Keywords : Sorting, parametric complexity, discrete uniform distribution, variance, the average case, worst case


Assistant Professor, Patna Women’s College, P.U.

Email-id :