EMPIRICAL ANALYSIS OF COMPARISON-BASED SORTING ALGORITHMS UNDER DIFFERENT DATA DISTRIBUTIONS

Introduction

Sorting is one of the most fundamental operations in computer science. It is widely used in database systems, search engines, and computational biology. The choice of a sorting algorithm can significantly affect the performance of an application, especially when processing large datasets. Theoretically, comparison-based sorting algorithms have a lower bound of O(n log n) comparisons. However, theoretical complexity does not always predict real execution time due to hardware-specific factors such as cache locality, branch prediction, and compiler optimizations. This study provides a comparative empirical analysis of four classical sorting algorithms: Quicksort, Mergesort, Heapsort, and Bubblesort. The main goal is to determine under what conditions an O(n²) algorithm can be competitive with O(n log n) algorithms.

Literature Review

The theoretical foundations of sorting algorithms are described in detail by Cormen et al. [1]. Knuth [2] provides a historical overview and rigorous complexity analysis. Sedgewick and Wayne [3] discuss practical implementations and performance tuning. Prior empirical studies have shown that Quicksort is often the fastest on random data, while Mergesort is preferred when stability is required. Heapsort guarantees O(n log n) time and O(1) extra memory. Bubblesort is rarely used in practice except for educational purposes or very small arrays. However, little attention has been paid to the boundary conditions where O(n²) algorithms may outperform O(n log n) algorithms due to lower overhead.

Problem Statement

The research question is formulated as follows: given a large unsorted array of integers, which sorting algorithm minimizes execution time and memory usage under different data distributions? The following constraints apply: (1) the array size ranges from 10³ to 10⁶ elements; (2) the input data can be random, nearly sorted, or reverse sorted; (3) the algorithm must be implemented in C++ with identical compiler optimizations.

Methodology

3.1 Experimental Setup

All experiments were conducted on a computer with an Intel Core i5-1135G7 processor (4 cores, 8 threads, 8 MB L3 cache), 16 GB DDR4 RAM, and Windows 11. The algorithms were implemented in C++ and compiled with GCC 12.2 using the -O2 optimization flag. Timing measurements were performed using std::chrono::high_resolution_clock with microsecond precision. Each experiment was repeated 10 times, and the average values were recorded.

3.2 Test Data Generation

Three types of input arrays were generated:

• Random array: uniformly distributed integers from 0 to 2³¹−1.
• Nearly sorted array: 95% of elements in correct order, 5% randomly permuted.
• Reverse sorted array: strictly descending order.

3.3 Measured Metrics

The following metrics were collected for each algorithm:

• Execution time (ms)
• Number of comparisons
• Number of assignments
• Peak memory usage (assessed analytically)

Results

4.1 Small Arrays (n = 500)

Table 1 shows the results for n = 500 under different data distributions.

Table 1.

Execution time (ms) for n = 500

For nearly sorted data, the optimized Bubblesort (with early termination) performed faster than Heapsort (0.08 ms vs. 0.17 ms). This supports the hypothesis that O(n²) algorithms can be competitive on small, almost ordered datasets.

4.2 Medium Arrays (n = 10,000)

Table 2.

Execution time (ms) for n = 10,000

At n = 10,000, the advantage of O(n log n) algorithms becomes clear on random and reverse sorted data. Quicksort shows a severe degradation on reverse sorted data (38.4 ms) due to poor pivot selection (last element). This is a known worst-case behavior.

4.3 Large Arrays (n = 500,000)

Table 3.

Execution time (ms) for n = 500,000

Bubblesort did not complete within a reasonable time (estimated > 30 seconds). For large arrays, O(n log n) algorithms are strictly superior. Quicksort remains the fastest on random and nearly sorted data but fails on reverse sorted arrays unless a random pivot is used.

Memory Complexity Analysis

Mergesort requires O(n) additional memory, which becomes critical for large n. For n = 500,000, Mergesort uses approximately 4 MB of extra memory (assuming 8-byte integers), while Quicksort and Heapsort use O(log n) and O(1) extra memory, respectively. Table 4 summarizes the memory requirements.

Table 4.

Additional memory required for sorting

Discussion

The experimental results confirm that theoretical O(n log n) complexity is not a perfect predictor of actual performance. Three key findings stand out:

1. Small and nearly sorted arrays: Optimized Bubblesort (with early termination) outperforms Heapsort and even Quicksort for n < 500. This is because the overhead of recursion and heap operations exceeds the cost of a linear scan when few swaps are needed.
2. Quicksort vulnerability: Without a randomized pivot, Quicksort degrades to O(n²) on reverse sorted data. In our experiments, execution time increased by a factor of 16 compared to random data.
3. Memory-performance trade-off: Mergesort provides stable, predictable performance across all input types but consumes O(n) extra memory. In memory-constrained environments, Heapsort is a better choice despite being slightly slower.

These results have practical implications. For sorting small arrays (e.g., in embedded systems or real-time applications), a hybrid approach (such as insertion sort for n < 50 and Quicksort for larger n) is recommended. For large-scale data processing, Quicksort with a random pivot is the best general-purpose choice unless stability is required.

Conclusion

This paper presented a comparative empirical analysis of four sorting algorithms. The main conclusions are:

1. For arrays smaller than 1000 elements, simple O(n²) algorithms can be competitive with O(n log n) algorithms, especially on nearly sorted data.
2. For arrays larger than 10,000 elements, O(n log n) algorithms are strictly superior.
3. Quicksort with a fixed pivot is vulnerable to worst-case inputs; a random pivot eliminates this issue.
4. Mergesort offers stable performance at the cost of additional memory.
5. Heapsort is the best choice when memory is severely limited.

Future work includes evaluating hybrid algorithms (e.g., Timsort used in Python), parallel sorting on multi-core systems, and the impact of compiler optimizations (-O3, -march=native) on performance.

References:

1. Cormen T. H., Leiserson Ch. E., Rivest R. L., Stein C. Introduction to Algorithms. — 3rd ed. — Cambridge : MIT Press, 2009. — 1312 p.
2. Knuth D. E. The Art of Computer Programming. Volume 3. Sorting and Searching. — 2nd ed. — Boston : Addison-Wesley, 1998. — 800 p.
3. Sedgewick R., Wayne K. Algorithms. — 4th ed. — Boston : Addison-Wesley, 2011. — 976 p.
4. GCC, the GNU Compiler Collection. Optimization Options [Electronic resource]. — Rezhim dostupa: https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html (data obrashcheniya: 14.05.2026).