AlgoBench-Sort - Implementation and Benchmarks of Sorting Algorithms

AlgoBench-Sort is a project whose purpose is to implement and analyze the time complexity of selected sorting algorithms.

The implemented algorithms include:

• Heap Sort
• Shell Sort
• Quick Sort
• Insertion Sort
• Hybrid Sort (Quick Sort combined with Insertion Sort)

The analysis takes the following factors into account:

• Impact of the data type on the performance of sorting algorithms (4-byte signed integers vs. floats).
• Initial distribution of values in arrays (Random, Sorted Ascending, Sorted Descending, Partially Sorted 33%, and Partially Sorted 66%).
• Impact of the choice of gap sequence in the Shell sort algorithm (classic Shell's sequence vs. Papiernow-Stasiewicz's sequence).
• Impact of the choice of pivot in the Quick Sort algorithm (Left, Right, Middle, and Random).
• Impact of the threshold size for the Hybrid Sort algorithm (testing thresholds of 8, 16, and 32).

Test Methodology

Because the algorithms are implemented in Java, running standard system time measurements can lead to inaccuracies due to JVM optimizations at runtime. To ensure highly precise measurements, the benchmarks were implemented using the JMH (Java Microbenchmark Harness) tool, which effectively eliminates noise caused by the JIT compiler and Garbage Collector.

Benchmark Configuration

The tests run in SingleShotTime mode. To ensure statistical reliability, each benchmark undergoes 10 warmup iterations followed by 100 measurement iterations. The time it takes to generate the data is strictly excluded from the benchmark results. To maintain data consistency without measuring array copying, JMH uses a @Setup(Level.Invocation) method to provide a fresh, pristine copy of the array for every single sorting operation.

Usage

The application features a Text User Interface (TUI) that allows you to interact with the project in two main ways:

• Benchmarking Mode
  • You can configure and launch the JMH benchmarks directly from the interface. The TUI utilizes an OptionsBuilder to let you select:
    • The data type (Integer or Float).
    • The array sizes.
    • The array distributions (e.g., Random, Sorted_ASC, Partially_Sorted).
    • The specific algorithms to test.
  • Once configured, the runner executes the benchmarks and exports the results to a structured CSV file for chart generation and further analysis.
• Verification Mode
  • This mode allows you to manually verify the correctness of the sorting algorithms.
  • Through the menu, you can load an array from a specified text file (where the first line defines the size, and subsequent lines are the array elements).

Key Findings

Based on the experiments conducted in this project, several significant conclusions were drawn:

• Data Type Overhead - Sorting operations on floating-point numbers (float) are systematically slower (by about 10-25%) than on integers (int). This is due to the more complex IEEE 754 memory representation and the computational overhead required by the processor and JVM to compare these values.
• Quick Sort Pivot Vulnerability - Choosing extreme edge elements (left or right) as pivots leads to a critical performance degradation to a time complexity of O(n^2) for monotonically sorted arrays. This deep recursion caused a StackOverflowError for arrays as small as 500,000 elements. Using a middle pivot completely resolved this issue, yielding excellent execution times.
• Hybrid Sort Optimization - When combining Quick Sort with Insertion Sort, a sub-array threshold of 32 elements provided the most optimal balance between reducing recursive calls and executing the insertion sort.
• Heap Sort Stability - Heap sort proved to be the most time-stable algorithm across all tests, consistently maintaining its O(nlogn) complexity regardless of how the initial data was distributed.