COMP20290 Algorithms Project

Improving Counting Sort Algorithm Via Data Locality

Group 15 - Aaron Peng, Sebastians Zudie, Sean Lawlor, Kristian Grey

---

Overview

This project implements and evaluates the hybrid sorting algorithm proposed in the paper "Improving Counting Sort Algorithm Via Data Locality" (Mahmud, Haque, Choudhury - ACMSE 2022). The algorithm combines a modified Quicksort preprocessing step with Counting Sort to reduce cache misses and improve practical performance over standard Counting Sort.

---

Project Structure

java/
├── Main.java                        Entry point, runs all three experiments
├── experiments/
│   ├── Experiment1.java             Counting Sort: random vs sorted input
│   ├── Experiment2.java             Hybrid vs plain Counting Sort (r >> n)
│   └── Experiment3.java             QS vs QS+IS vs QS+CS comparison
├── alg/
│   ├── Timer.java                   Benchmarking utility
│   ├── Util.java                    General helpers (average etc.)
│   ├── TimeCounter.java             Accumulates timing across iterations
│   ├── Graphs.java                  Swing-based graph rendering
│   └── sorting/
│       ├── CountingSort.java        Counting Sort implementation
│       ├── QuickSort.java           Standard QS, Modified QS + CS, Modified QS + IS
│       ├── InsertionSort.java       Insertion Sort implementation
│       ├── SortUtil.java            Array generation, partition, min/max helpers
│       └── TriConsumer.java         Functional interface for 3-argument tasks
└── testing/
    └── Testing.java                 JUnit tests for correctness verification

---

Requirements

• Java 11 or higher
• JUnit 4 (for running tests)

---

How to Compile

From the java/ directory:

javac -d out Main.java experiments/*.java alg/*.java alg/sorting/*.java

---

How to Run

Run all experiments and print to console:

java -cp out Main

Run all experiments and save output to a file:

java -cp out Main results.txt

Output will include benchmark results for all three experiments with average runtimes printed in milliseconds.

---

How to Run Tests

First download both required JARs (JUnit 4 depends on Hamcrest):

curl -O https://repo1.maven.org/maven2/junit/junit/4.13.2/junit-4.13.2.jar
curl -O https://repo1.maven.org/maven2/org/hamcrest/hamcrest-core/1.3/hamcrest-core-1.3.jar

macOS / Linux:

javac -cp .:junit-4.13.2.jar:hamcrest-core-1.3.jar -d out testing/Testing.java alg/sorting/*.java
java -cp .:junit-4.13.2.jar:hamcrest-core-1.3.jar:out org.junit.runner.JUnitCore testing.Testing

Windows:

javac -cp .;junit-4.13.2.jar;hamcrest-core-1.3.jar -d out testing/Testing.java alg/sorting/*.java
java -cp .;junit-4.13.2.jar;hamcrest-core-1.3.jar;out org.junit.runner.JUnitCore testing.Testing

Both tests sort a random array of 1000 integers and compare the result element-by-element against Arrays.sort to verify correctness.

---

Experiments

Experiment	What it tests	Key variables
1	Effect of input ordering on Counting Sort	N = R = 1M, 2M, 3M
2	Impact of preprocessing on Counting Sort	N = 1K–3K, R = 1M
3	QS vs QS+IS vs QS+CS head-to-head	N = R = 1M, 2M

Each experiment runs 10 iterations per configuration and reports the average runtime.

---

Threshold Parameter (C)

The modified Quicksort stops recursing on a partition when:

(maxValue - minValue) + (high - low) <= C

All experiments use C = 1000 as specified in the paper. This ensures each partition's auxiliary arrays fit within CPU cache during the Counting Sort phase.

---

Reproducing the Paper's Results

The paper ran on an Intel Core i7-7500U (32KB L1 data cache, 256KB L2 cache). Our tests were run on an Apple MacBook Pro with an M4 Pro chip (128KB L1 data cache per performance core). Absolute runtimes will differ - our times are roughly half those in the paper due to the significantly larger cache - but the relative ordering and scaling ratios between algorithms should match closely.