Conventional Vs Enhanced Sorting Algorithm: A Review

International Journal of Research and Scientific Innovation (IJRSI) | Volume V, Issue I, January 2018 | ISSN 2321–2705

Conventional Vs Enhanced Sorting Algorithm: A Review

Pooja Gupta

 Assistant Professor, Uttaranchal University, Dehradun, Uttarakhand, India

Abstract: Sorting problem is one of the most antique problems of computer science. From the beginning of computation, algorithms for sorting problem has been derived and analyzed by many researchers. The first sorting algorithm derived was bubble sort (1956). Many useful sorting algorithms are continually being invented like Merge sort, Timsort (2002), Library sort (2006). A vast number of sorting algorithms and their enhancements exists in the literature. One would really like to know that these enhancements of sorting algorithms are actually better than the conventional sorting algorithms. For this purpose authors have taken a case of classical merge sort and enhanced merge sort algorithm proposed by paira et al [12]. authors have tested the performance of both the algorithms using different random number distributions and found that there is no significant difference between the algorithms.

Keywords: Algorithm, Sorting, Efficiency, Time Complexity, Space Complexity

I. INTRODUCTION

In computer science sorting problem has been researched at length. Several sorting algorithms and enhancement of classical sorting algorithm have been proposed, for example, merge sort was proposed in 1981 and its enhancement algorithm is proposed in 2016. Several enhancements of classical sorting algorithms have been presented in the literature [1, 2, and 3]. Out of all available sorting algorithms which one is most suitable for an application depends on many parameters like input size, type of data and distribution of data [4]. Other factors that influence the performance of sorting algorithm are number of comparison operations, number of swaps required, and memroy space [5]. In literature, there are many sorting algorithms to solve a particular problem and there is a drastic difference in their performance and efficiency. The difference in efficiency is much more important than differences due to changes in hardware and software of the system [6]. [7, 8] derived quick sort algorithm and many researchers considered QuickSort algorithm to be the fastest sorting algorithms [9, 10, 11]. The particular algorithm one chooses depends on the properties of data and the operations one may perform on the data [5].

Read More