go_sorting - Sorting Algorithm Benchmarking Suite

A comprehensive Go-based benchmarking suite for comparing the performance of various sorting algorithms across different data distributions and input sizes.

Origin

This project originates from the bachelor thesis:

"Entwurf, Implementierung und Evaluierung eines Sortier-Algorithmus für zeitbasierte Daten" (Design, Implementation and Evaluation of a Sorting Algorithm for Time-Based Data)

• Author: Maximilian Dollinger
• University: IU Internationale Hochschule, B.Sc. Wirtschaftsinformatik
• Supervisor: Prof. Dr. Cornelia Heinisch
• Submission Date: 27.11.2023

The thesis designs and evaluates the TimeSort algorithm — a radix-sort variant specialized for timestamped data — achieving up to 8x speedup over Go's standard library sort while trading off memory usage. The algorithm combines insertion sort, in-place American Flag Sort, and parallelized radix sort strategies with data-order detection for optimal performance.

The full thesis is included in this repository as thesis.pdf.

Overview

go_sorting is a performance evaluation tool that benchmarks multiple sorting algorithms using configurable data generators and input sizes. It provides detailed timing measurements, memory usage statistics, and generates formatted reports for analysis.

Features

Sorting Algorithms

The project implements and benchmarks the following sorting algorithms:

• Insertion Sort - Simple comparison-based algorithm, efficient for small datasets
• Radix Sort - Non-comparative integer sorting algorithm (LSD)
• American Flag Sort - In-place variant of radix sort (Experimental with non-recursive implementation)
• American Flag Sort (Parallel) - Multi-threaded version of American Flag Sort
• TimeSort - Composite algorithm combining insertion sort, order detection, and radix-sort variants optimized for time-based data (from thesis)
• Standard Sort - Go's built-in sort.Slice() implementation

Radix sort and American Flag sort are based on the Paper: McIlroy, D. (1993). Engineering Radix Sort.

Data Generators

Multiple data distribution patterns are available for testing:

• Random - Randomly distributed integers
• Sorted - Already sorted ascending data
• Reversed - Reverse-sorted (descending) data
• SortedDoubled - Two concatenated sorted sequences
• NearSorted - Mostly sorted data with some random swaps

Installation

Prerequisites

• Go 1.24.5 or higher

Setup

1. Clone the repository:

git clone https://github.com/maxdolliger/go_sorting.git
cd go_sorting

2. Build the project:

go build

Usage

Basic Execution

Run the benchmarking suite with default settings:

./go_sorting

Configuration

The main configuration is in main.go:

sortingSliceSizes := []int{10, 100, 1000, 10_000, 100_000, 1_000_000}
runsPerSize := 1

• sortingSliceSizes: Array sizes to test
• runsPerSize: Number of iterations per size for averaging

Output

The program generates:

1. Console output: Formatted table showing performance results
2. File output: Timestamped results file (e.g., Random_2024-01-15_14-30-45.txt)

Benchmarking

Metrics Collected

For each algorithm and input size:

• Execution Time: Precise timing using time.Since()
• Memory Usage: Memory snapshots during execution
• Correctness Verification: Ensures data is properly sorted
• Garbage Collection: Forced GC between runs for consistent measurements

Project Structure

go_sorting/
├── main.go                    # Entry point and orchestration
├── executer.go               # Benchmark execution engine
├── go.mod                    # Go module definition
├── LICENSE.md                # Project license
├── benchmarks/               # Benchmark test files
│   ├── bench_key_test.go
│   ├── bench_less_test.go
│   └── bench_sort_test.go
├── data/                     # Data generation and evaluation
│   ├── eval.go              # Performance evaluation logic
│   ├── format.go            # Output formatting
│   ├── generator.go         # Test data generators
│   └── table.go             # Table formatting utilities
└── sorting/                  # Sorting algorithm implementations
    ├── types.go             # Common interfaces and types
    ├── insertionSort.go     # Insertion sort implementation
    ├── radixSort.go         # Radix sort implementation
    ├── americanFlagSort.go  # American flag sort implementation
    ├── americanFlagSortP.go # Parallel American flag sort
    ├── timeSort.go          # TimeSort composite algorithm (from thesis)
    └── stdSort.go           # Standard library wrapper

License

This project is licensed under the GLWTS (Good Luck With That Shit) Public License. See LICENSE.md for details.

Author

Created by @maxdolliger

---

Note: This benchmarking suite is designed for educational and research purposes. Results may vary based on hardware, Go version, and system load.