Analisis Komparatif Efisiensi AlphaDev dan Algoritma Sorting Konvensional pada Implementasi C++

Abstract

Data sorting is a fundamental component of modern computing, especially when handling large-scale datasets, where time efficiency and memory usage are critical to system performance. Over the past decades, classical algorithms such as Quick Sort, Merge Sort, and Insertion Sort have been extensively optimized and widely implemented in the C++ standard library. Recent developments in artificial intelligence have introduced a new approach through AlphaDev, a deep reinforcement learning agent that successfully discovered small-scale sorting routines more efficient than manually optimized code, which have since been integrated into the C++ LLVM library. This study conducts a comparative analysis between AlphaDev’s sorting routines and conventional algorithms commonly used in C++ implementations, namely Insertion Sort, Introsort (as represented by std::sort), and Merge Sort. The comparison is based on two primary metrics: execution time (µs/ms) and additional memory consumption (auxiliary space). Testing was performed on integer-type data of varying sizes and distributions, ranging from small sorts (N ≤ 30) to large-scale datasets (N up to 10⁶), with each scenario executed repeatedly to obtain stable average runtimes. Experimental results show that for very small arrays (N ≤ 30), AlphaDev consistently outperforms Insertion Sort by approximately 15–30% and is about 5–12% faster than the conventional Introsort base case. When integrated as the base case within Introsort for large-scale sorting, AlphaDev’s routines deliver an aggregate performance improvement of around 1–2% compared to standard Introsort. In terms of memory usage, both AlphaDev and Insertion Sort maintain O(1) space complexity with negligible additional memory, whereas Merge Sort requires O(N) auxiliary space, making it the most memory-intensive algorithm in this evaluation. These findings reaffirm that no single sorting algorithm is optimal for all conditions: AlphaDev is particularly well-suited for small-scale sorting and effective as a base case in hybrid algorithms, while divide-and-conquer approaches such as Introsort remain dominant for large datasets. This study provides empirical evidence that integrating AI-discovered algorithms into programming language libraries can yield measurable performance gains, which, although seemingly modest in percentage terms, are significant in large-scale computational workloads.