DISTRIBUTION-SENSITIVE BENCHMARKING OF CLASSICAL AND ODD-EVEN PARITY BASED SORTING ALGORITHMS ACROSS STATISTICAL DATA MODELS

Abstract

The sorting algorithms are essential entities in computer science, physics, biology  and assist in  a broad spectrum of data-intensive applications such as databases, search systems, operating platforms and big data analysis of biological data. In DNA sequence organization and genomic processing, where huge datasets have to be handled, efficient sorting is especially essential. Theoretical analysis often focused on time and space complexity of these algorithms, the statistical properties of input data can be very important in practice. This paper investigates how positive integers datasets generated from nine statistical distributions influence the sorting behavior of eight sorting algorithms: Merge Sort, Heap Sort, Quick Sort, Shell Sort, Bubble Sort, and Insertion Sort, and the non comparative Radix Sort, as well as recently developed Odd-Even Parity Based sorting algorithm (OEPB). The primary criterion of evaluation is the execution time, and several trials are done to provide consistency and reliability of the results. The findings suggest that the performance of algorithms can be different in various data distributions. The specific focus is put on the OEPB algorithm that does exhibit a significant space efficiency with the gradually reduced memory consumption as the execution time proceeds. This feature renders it particularly appropriate in low memory resources settings. Whilst algorithms with complexity O (n log2 n) tend to be dominant, the findings emphasize the role of memory efficiency in design and sensitivity to input properties in determining the choice of sorting algorithms in practice.