Automating algorithm experiments with ALGator

Background: Theoretical algorithm analysis provides fundamental insights into algorithm complexity but relies on simplified and often outdated computational models. Experimental algorithmics complements this approach by evaluating the empirical performance of algorithm implementations on real data and modern computing platforms. However, the absence of standardized, reproducible experimental environments limits the reliability and comparability of results. Objective: This work aims to establish a formal and reproducible framework for algorithm experimentation and to provide a practical platform that enables researchers to model problems, execute experiments, and share results transparently. Methods: We propose a comprehensive experimentation model that formalizes all key entities of algorithm evaluation, including inputs, outputs, test cases, test sets, parameters, algorithms, and performance indicators. The model is implemented in ALGator, an open-source system that automates test case generation, algorithm execution, output validation, and result presentation, while supporting collaborative development and public dissemination of experiments. Results: The capabilities of ALGator are demonstrated through a case study on the array-sorting problem. Experiments comparing Hoare’s and Yaroslavskiy’s Quicksort implementations reveal nuanced performance differences: Hoare’s version excels on random inputs without duplicates, whereas Yaroslavskiy’s performs substantially better when input data contain many duplicates. All experimental data and configurations are openly available through the ALGator platform. Conclusion: The combination of a formal experimental model and its open-source implementation in ALGator provides a robust foundation for reproducible experimental algorithmics. This approach promotes transparency, facilitates independent verification, and enables researchers to extend existing experiments with new test cases and performance metrics, advancing the reproducibility and reliability of empirical algorithm evaluation.