Abstract

Aim/Background: Insertion Sort is widely taught in computer science, yet its practical runtime can vary substantially depending on the programming language and the structure of the input data. This study aims to provide a language-aware empirical comparison of Insertion Sort and to complement benchmark results with machine-learning–based runtime classification.
Methods: Insertion Sort was implemented and evaluated in six languages (C, C++, Go, Java, PHP, and Python). Execution time was measured under a controlled hardware/software environment using identical datasets of three sizes (1,000; 10,000; and 100,000 elements) and four input patterns (ascending, descending, nearly sorted, and random). To interpret performance trends, supervised machine learning models were trained to classify runtime behavior into Fast, Moderate, and Slow categories, and a Relative Execution Time Ratio (RETR) metric was introduced to normalize runtimes against the fastest observed case.
Results: Go achieved the best overall performance, followed by Java, while C and C++ produced mid-range results. Python and PHP were consistently the slowest, with the largest slowdowns observed for large and reverse-ordered inputs. For runtime classification, Random Forest outperformed XGBoost, achieving 93% accuracy compared with 87% for XGBoost. RETR enabled a clearer cross-language comparison by standardizing runtimes relative to the fastest baseline.
Conclusion: Insertion Sort performance is strongly influenced by both programming language and input characteristics. Combining benchmarking with ML-based classification and normalized metrics (RETR) offers a more interpretable view of runtime behavior and supports better alignment of algorithm choices with language and data context in real-world applications.

Key words: Keywords— Insertion Sort, Programming Languages, Runtime Performance, Data Patterns, Machine Learning, Random Forest, XGBoost, Relative Execution Time Ratio (RETR)