Sorting Algorithm Benchmark

A Java project comparing the performance of three sorting algorithms — Insertion Sort, Counting Sort, and Radix Sort — across different array sizes and orderings.

Overview

This project measures how each algorithm's operation count and runtime are affected by:

• Input size — from 100 to 1,000,000 elements
• Input ordering — sorted, reversed, random, and mixed (half sorted, half random)

The goal is to build intuition for why algorithmic complexity matters in practice, not just in theory. Each algorithm has different strengths depending on the shape of the input data.

Project Structure

File	Description
AlphaNumeric.java	Test data object with a 6-character string field and an integer field
ArrayMaker.java	Builds test arrays in sorted, reversed, or random order
Sorter.java	Common interface implemented by all sorting algorithms
Insertion.java	Insertion Sort (and Shell Sort via configurable step size)
Counting.java	Counting Sort, keyed on the integer field
Radix.java	Radix Sort, built on top of Counting Sort
Main.java	Runs the full benchmark suite and writes results to results.csv

How It Works

Each AlphaNumeric object has two fields:

• an alpha string (always 6 lowercase letters)
• a number integer (0 to 999,999)

ArrayMaker generates arrays in three flavors:

• Sorted — numbers increase, alphas decrease
• Reversed — numbers decrease, alphas increase (worst case for Insertion Sort)
• Random — both fields randomly generated

All three sorters implement the Sorter<T> interface, which requires:

• sort(T[] array) — sorts in place
• sort(T[] inArray, T[] outArray) — sorts without modifying the original
• getCount() — returns the operation count from the last sort, used to measure cost independent of wall-clock time

Algorithms

Insertion Sort

Sorts by repeatedly picking the next element and shifting it left into its correct position among the already-sorted elements. Best case (already sorted) is O(n); worst case (reversed) is O(n²). The step parameter also allows it to run as a single Shell Sort pass with a wider gap.

Counting Sort

Counts how many elements share each key value, then uses those counts to place every element directly into its final position — no comparisons needed. Runs in O(n + k), where k is the range of key values. Stable: equal keys preserve their original relative order.

Radix Sort

Sorts integer keys one digit at a time, from least significant to most significant, using Counting Sort as the underlying digit sorter. Because Counting Sort is stable, the ordering from each pass carries through to the next. Runs in O(d · n), where d is the number of digits in the largest key.

Running the Benchmark

Compile and run from the parent directory of the Main/ folder:

javac Main/*.java
java Main.Main

This runs all three algorithms across six array sizes (100 to 1,000,000) and four orderings (sorted, reversed, random, mixed). Results are printed to the console and written to results.csv in the directory where you ran the command.

Note: Insertion Sort is skipped on reversed/random arrays above n = 100,000 by default, since its O(n²) behavior makes those runs take several minutes. You can remove that guard in Main.java if you want the full dataset.

Output Format

Each line of results.csv follows this format:

Algorithm,ArrayType,n,OperationCount,TimeMs

For example:

Insertion,reversed,1000,500499,3
Counting,random1,1000,1996771,1
Radix,sorted,1000,7000,0

Key Findings

• Insertion Sort is fast on nearly-sorted data but degrades sharply (O(n²)) on reversed or random input.
• Counting Sort has consistent performance regardless of array order, but its cost depends on the range of key values rather than just n — random arrays with a wide value spread cost more than sorted/reversed arrays with a narrow one.
• Radix Sort scales predictably with n and is largely unaffected by input ordering, making it a strong general-purpose choice when keys are bounded integers.