Google’s DeepMind AI Shatters Records with a 70% Faster Sorting Algorithm

Google's artificial intelligence subsidiary, DeepMind, has made another striking discovery. In a new paper published today in Nature, researchers revealed that it found a sorting algorithm that's 70% faster than the previously best-known method in C++, a feat that promises to have far-reaching implications in the world of computing.

As computer chips approach fundamental physical limits due to their nanoscale transistors, the need for better software efficiency and optimization becomes increasingly paramount. The promise of the new sorting algorithm from DeepMind could provide much-needed relief as AI serves as a critical partner in discovering new optimization pathways.

The recent achievement came about by adapting the AlphaZero AI, which famously mastered complex games like chess and Go, into a code-focused version dubbed AlphaDev. The AlphaDev AI was able to unleash the same reinforcement learning prowess that had mastered games by treating a basket of complex computer instructions as a potential set of game moves.

Working in assembly language — a low-level programming language that provides explicit instructions for manipulating numbers on a chip — AlphaDev demonstrated its potential to reshape our understanding of code efficiency. While most programmers work in high-level languages like C++ that are translated into assembly at runtime, it's the efficiency of these assembly-level instructions that ultimately dictate the performance of a program.

DeepMind's researchers focused their efforts on sorting algorithms for lists of three to five items. While it may seem insignificant, these elementary sorting algorithms form the building blocks of more advanced computational tasks, executed trillions of times each day across the globe. Therefore, any improvements to these rudimentary algorithms could have an outsized impact.

These same short algorithms have also been the subject of human scrutiny and optimization for decades, with the last sorting algorithm update to C++ arriving over one decade ago. Yet, AlphaDev proved that there was still room for improvement.

AlphaDev discovered that a three-item sorting algorithm, whose best human version was implemented in 18 instructions, could be reduced to just 17 instructions. Similarly, a sorting algorithm for a list of five items that usually required 46 instructions was achieved in only 42 steps. Shortening a sorting algorithm by just 4 instructions created a 70% speed increase.

This discovery not only surprised DeepMind's own researchers but also exemplified the AI's uncanny ability to find unconventional yet effective solutions. This same potential was demonstrated in 2016 when DeepMind's AlphaGo AI defeated the reigning human champion with an unexpected “weird” series of moves that had never been contemplated by human grandmasters in Go.

Beyond the realm of algorithms, DeepMind’s research has also brought progress to the biology sector. In a span of just 18 months, DeepMind’s AlphaFold AI predicted the protein structure of all known proteins to date — a staggering total of over 200 million structures.

“We honestly didn’t expect to achieve anything better” than existing algorithms, said Daniel Mankowitz, a research scientist at Google DeepMind. “But to our surprise, we managed to make it faster. We initially thought this was a mistake or a bug or something, but when we analyzed the program we realized that AlphaDev had actually discovered something.”