Почему обработка отсортированного массива выполняется быстрее, чем неотсортированного?

Причина — предсказание переходов (branch prediction)

Вы столкнулись с классическим эффектом, связанным с архитектурой современных процессоров. Дело не в алгоритме или компиляторе, а в том, как CPU обрабатывает условные переходы (ветвления).

Современные процессоры используют конвейерную архитектуру (pipelining). Чтобы ускорить выполнение, они загружают в конвейер несколько команд заранее. Когда встречается условный переход (например, if (data[i] >= 128)), процессор не знает, какая ветка будет выполнена — if или else. Он делает предположение с помощью механизма предсказания переходов (branch prediction).

Если предсказание верное — конвейер продолжает работу без задержек. Если ошибочное — конвейер нужно очистить и загрузить правильные команды, что вызывает потерю тактов (pipeline flush).

Как это работает в вашем примере

• Отсортированный массив: сначала все элементы меньше 128 (условие ложно), потом все больше или равны 128 (условие истинно). Процессор быстро «запоминает» паттерн: после серии «нет» идёт серия «да». Предсказание почти всегда верное.
• Неотсортированный массив: значения 0–255 чередуются случайным образом. Условие может быть то истинным, то ложным. Процессор ошибается примерно в 50% случаев, что приводит к постоянным очисткам конвейера.

Демонстрация на C++

Вот код, который симулирует эту разницу и показывает количество правильных/ошибочных предсказаний (только для x86 с использованием встроенных счётчиков, но для понимания хватит замеров времени):

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>

int main() {
    const int SIZE = 100000;
    std::vector<int> data(SIZE);
    
    // Заполняем случайно
    for (auto& x : data) x = rand() % 256;
    
    // Сортированная копия
    std::vector<int> sorted = data;
    std::sort(sorted.begin(), sorted.end());
    
    auto test = [&](const std::vector<int>& arr, const char* name) {
        long long sum = 0;
        auto start = std::chrono::high_resolution_clock::now();
        for (int x : arr) {
            if (x >= 128) sum += x;  // проблемное место
        }
        auto end = std::chrono::high_resolution_clock::now();
        auto ms = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        std::cout << name << ": " << ms << " мкс\n";
    };
    
    test(sorted, "Sorted");
    test(data, "Unsorted");
    
    // А теперь — хитрость: убираем ветвление с помощью тернарного оператора
    // Компилятор может заменить его на CMOV (conditional move)
    std::cout << "\nБез ветвления (через тернарный):\n";
    
    auto test_no_branch = [&](const std::vector<int>& arr, const char* name) {
        long long sum = 0;
        auto start = std::chrono::high_resolution_clock::now();
        for (int x : arr) {
            sum += (x >= 128) ? x : 0;  // нет if — нет branch misprediction
        }
        auto end = std::chrono::high_resolution_clock::now();
        auto ms = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        std::cout << name << ": " << ms << " мкс\n";
    };
    
    test_no_branch(sorted, "Sorted");
    test_no_branch(data, "Unsorted");
    
    return 0;
}

Как это исправить?

• Использовать тернарный оператор — компилятор часто генерирует инструкцию CMOV (conditional move), которая не зависит от предсказания ветвлений.
• Переписать логику без ветвления (например, с помощью битовых операций).
• Использовать std::partition или другие алгоритмы, которые минимизируют случайные ветвления.
• Включить оптимизацию компилятора (-O2 или -O3 для GCC/Clang, /O2 для MSVC) — компилятор может сам заменить ветвление на безусловные инструкции.

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

// Вместо if
sum += (x >= 128) * x;  // если x >= 128, то (1) * x, иначе (0) * x
// Или через маску:
int mask = (x - 128) >> 31;  // все биты 1, если x < 128
sum += x & ~mask;            // обнуляем x, если условие ложно