В июне 2023 года компания DeepMind из Google опубликовала в журнале Nature плодотворную статью, в которой объявила, что их программист искусственного интеллекта AlphaDev обнаружил несколько новых алгоритмов сортировки, которые могут улучшить сортировку коротких последовательностей до 70%.

Это удивительно. Сортировка остается основополагающим принципом в области информатики: множество алгоритмов сортировки прошли десятилетия тщательного изучения. Что именно предложил AlphaDev?

К сожалению, сообщение в блоге DeepMind об их открытии скорее вводит в заблуждение, чем помогает. sort3 (алгоритм сортировки трех чисел) в их сообщении просто сортируется неправильно. В их сообщении упущен тот важный факт, что их sort3 является лишь фрагментом реального sort3.

Учитывая это упущение, я начну с нуля и выведу этот новый алгоритм sort3 в пошаговом повествовании, управляемом человеком. Это не только прольет свет на ошибки нашего алгоритма в прошлом, но и проложит путь для будущих улучшений. В статье DeepMind содержится больше алгоритмов, чем sort3. Но для простоты в ходе нашего обсуждения мы сосредоточимся только на этом.

1. Обязательное условие

Новый алгоритм сортировки AlphaDev обнаруживается на уровне ассемблерного кода. Но не волнуйтесь, если вы не знакомы с этим компьютерным языком низкого уровня. Все, что вам нужно знать, это следующие три простых инструкции:

mov A B : move a value from source A to destination B
cmp A B : compare the values in A and B, and set a register flag accordingly
cmovX A C: Conditionally move the value from A to C given the register flag
        where "X" could be 
        l (less than), 
        g (greater than), 
        le (less than or equal to), or 
        ge (greater than or equal to).

Обладая вышеуказанными знаниями, мы готовы понять прорыв в области сортировки AlphaDev.

2. Возвращаясь к исходной реализации sort3

Давайте сначала попробуем решить эту проблему самостоятельно. Можно сформулировать алгоритм сортировки трех чисел, подобный следующему:

// sort3(P, Q, R)
if (Q > R) swap(Q, R);  // sort2(Q, R)
if (P > R) swap(P, R);  // sort2(P, R)
if (P > Q) swap(P, Q);  //…