Approximate Sorting Algorithm & Performance Comparison Benchmark Program

[kimpro82]

1. Project Overview

• Objective: Develop a Python CLI benchmarking program to objectively compare and verify the performance (speed and accuracy) of 4 approximate sorting algorithms—which allow for errors instead of insisting on 100% perfect sorting—across various data distribution environments.
• Environment & Tech Stack: Python 3, NumPy, Numba (@njit), executed in GitHub Codespaces with VS Code and terminal.
• Scope:
  • Implementation of 4 approximate sorting algorithms using Numba for native-level execution speed.
  • 3 data distribution generators (Uniform, Normal, Exponential).
  • Performance evaluation engine (Isolated speed measurement with warm-up calibration and multi-dimensional accuracy verification).
  • Console-based text table output (Visualization is separated into Phase 2).

2. Project File Structure

The project will be structured cleanly within GitHub Codespaces as follows:

approx-sort-benchmark/
│
├── benchmark.py       # Main orchestration, dataset generation, evaluation loop, and output
├── algorithms.py      # Module containing the 4 approximate sorting algorithms optimized with Numba
└── requirements.txt   # Dependencies (numpy, numba, matplotlib)

3. Target Algorithms & Detailed Specifications

1. Naive Interpolation Sort

• Detailed Operation Principle:
  1. Performs a single pass to find the minimum (min) and maximum (max) values of the entire dataset.
  2. Re-traverses the data, scaling each element's value linearly within the min-max range to calculate an approximate array index (placement position).
  3. If another value already exists at that index (collision), it places the new value in the first available empty index to the right if larger, or to the left if smaller.
• Time Complexity:
  • Average/Best: O(n) (when data is uniformly distributed)
  • Worst: O(n^2) (when collisions explode due to extreme outliers, increasing linear probing overhead)

2. Asymmetric Range Interpolation Sort

• Detailed Operation Principle:
  1. Performs a single pass to simultaneously find min, max, and the overall average (mean).
  2. To defend against skewed distributions, it sets the core densely populated 'Standard Range' using min(max - avg, avg - min) as the radius.
  3. Outliers falling outside the Standard Range are isolated into a separate +1 outlier bucket.
  4. Divides the inside of the Standard Range into sqrt(n) + 1 intervals to place the data.
• Time Complexity:
  • O(n) (2-pass: 1 pass for profiling, 1 pass for sorting/placement)

3. Adaptive Quantile Bucket Sort

• Detailed Operation Principle:
  1. Performs the 1st pass to identify min, max, and the overall average.
  2. Performs the 2nd pass to find the average of values lower than the overall average (mu_low) and higher than the overall average (mu_high).
  3. Uses these 3 average values as anchor points to split the data space into 4 quarter-skeletons.
  4. Reflects the data density ratio (n_low, n_high, etc.) within each quarter-skeleton to dynamically configure a total of sqrt(n) + 1 bucket boundaries (index ranges).
• Time Complexity:
  • O(n) (Multi-pass profiling with a constant number of passes)

4. Coarse Block Approximate Sort

• Detailed Operation Principle:
  1. Prepares a total of sqrt(n) + 1 bucket intervals finalized through the adaptive bucket structure or standard range settings above.
  2. Traverses the data, classifying each element into its corresponding bucket (push_back).
  3. Drastically omits the internal sorting operation (O(n log n)) and simply concatenates the buckets in order to quickly secure only the macro-level sorting state (C-sorted).
• Time Complexity:
  • O(n) (Optimized with 2-pass and sequential memory copy operations)

4. Test Dataset Definitions

To clearly compare the strengths and weaknesses of the algorithms, the following 3 distributions are used. (Data size N is adjustable as a parameter, default example: N = 100,000)

• Uniform Distribution: Form where data is evenly spread across all intervals.
• Normal Distribution: Bell-shaped form where data is concentrated in the center and thin at both ends.
• Exponential Distribution: Asymmetric form heavily skewed to one side with a long tail.

5. Evaluation Metrics & Benchmarking Guidelines

① Speed Performance & Warm-up Calibration

• Numba Acceleration: Core sorting functions in algorithms.py must use the @njit(nopython=True) decorator to bypass Python interpreter overhead.
• Warm-up Runs (Calibration): To prevent JIT compilation overhead from skewing initial execution time measurements, execute 1–2 dry runs (warm-up) before starting the formal measurement loop.
• Measurement Method: Run each algorithm independently 50 to 100 times in an isolated single-thread environment.
• Recorded Metrics: Median and Minimum (Best) execution times (Unit: milliseconds, ms).

② Accuracy Metrics (Averaged over $n$ runs)

Compared against a perfect sorting result (Standard Sort, e.g., Python's built-in sort()) for each experimental run to measure the following two indicators, ultimately yielding the average over $n$ runs:

1. Displacement Error:
   • Average Position Displacement: Overall average of absolute index differences (|i_true - i_approx|).
   • Maximum Position Displacement: The worst-case error tolerance guaranteed by the algorithm ($C$ in $C$-sorted).
2. Non-parametric Rank Statistics:
   • Spearman's Footrule: Calculated as the sum of absolute rank differences (|R_true - R_approx|); normalized. Closer to 0 means convergence to a perfect sort.

6. Implementation Milestones

• Step 1: Set up directory structure, requirements.txt, and data generation module (Uniform, Normal, Exponential distribution data generators using NumPy).
• Step 2: Implement core logic for the 4 approximate sorting algorithms in algorithms.py utilizing Numba (@njit).
• Step 3: Implement evaluation measurement module in benchmark.py (Position displacement, Spearman's footrule calculator, warm-up calibration, and isolated timing loops).
• Step 4: Implement console text table output formatter and run integration tests via GitHub Codespaces terminal.