Modified blockQuicksort with three element rule vs Standard blockQuicksort

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>
#include <iomanip>
#include <cmath>

// Modified blockQuicksort with three element rule vs Standard blockQuicksort
// Contact Email [email protected]
// Created by I.A

void apply_three_element_rule(std::vector<int>& arr, int low, int high) {
    if (high - low == 2) {
        int pivot = arr[low];
        int third_num = arr[high];

        if (third_num <= pivot) {
            int temp_mid = arr[low + 1];
            arr[high] = temp_mid;
            arr[low + 1] = pivot;
            arr[low] = third_num;
        } else {
            int temp_mid = arr[low + 1];
            arr[low] = temp_mid;
            arr[low + 1] = pivot;
            arr[high] = third_num;
        }
    }
}


// Pure BlockQuicksort

void blockQuicksortUnmodified(std::vector<int>& arr, int low, int high) {
    if (low >= high) return;

    if (high - low == 1) {
        if (arr[high] < arr[low]) std::swap(arr[low], arr[high]);
        return;
    }

    int mid = low + (high - low) / 2;
    if (arr[mid] < arr[low])  std::swap(arr[low], arr[mid]);
    if (arr[high] < arr[low]) std::swap(arr[low], arr[high]);
    if (arr[high] < arr[mid]) std::swap(arr[mid], arr[high]);

    int pivot = arr[mid];
    std::swap(arr[mid], arr[high]);

    constexpr size_t BLOCK_SIZE = 64;
    int left_offsets[BLOCK_SIZE];
    int right_offsets[BLOCK_SIZE];

    int i = low;
    int j = high - 1;

    int num_left = 0, num_right = 0;
    int idx_l = 0, idx_r = 0;
    int start_l = 0, start_r = 0;

    while (true) {
        if (num_left == 0) {
            if (i > j) break;
            start_l = i;
            int block = std::min<int>(BLOCK_SIZE, j - i + 1);
            for (int k = 0; k < block; ++k) {
                left_offsets[num_left] = k;
                num_left += (arr[i + k] >= pivot);
            }
            i += block;
            idx_l = 0;
        }

        if (num_right == 0) {
            if (i > j) break;
            int block = std::min<int>(BLOCK_SIZE, j - i + 1);
            start_r = j - block + 1;
            for (int k = block - 1; k >= 0; --k) {
                right_offsets[num_right] = k;
                num_right += (arr[start_r + k] < pivot);
            }
            j -= block;
            idx_r = 0;
        }

        int min_swaps = std::min(num_left, num_right);
        for (int k = 0; k < min_swaps; ++k) {
            std::swap(arr[start_l + left_offsets[idx_l + k]],
                      arr[start_r + right_offsets[idx_r + k]]);
        }

        num_left -= min_swaps;
        num_right -= min_swaps;
        idx_l += min_swaps;
        idx_r += min_swaps;
    }

    int split;
    if (num_left > 0) {
        int last_less = i - 1;
        for (int k = num_left - 1; k >= 0; --k) {
            std::swap(arr[start_l + left_offsets[idx_l + k]], arr[last_less]);
            last_less--;
        }
        split = last_less + 1;
    } else if (num_right > 0) {
        int first_greater = j + 1;
        for (int k = num_right - 1; k >= 0; --k) {
            std::swap(arr[start_r + right_offsets[idx_r + k]], arr[first_greater]);
            first_greater++;
        }
        split = first_greater;
    } else {
        split = i;
    }

    std::swap(arr[split], arr[high]);

    blockQuicksortUnmodified(arr, low, split - 1);
    blockQuicksortUnmodified(arr, split + 1, high);
}


// 2. Modified BlockQuicksort with Custom Rule

void blockQuicksortModified(std::vector<int>& arr, int low, int high) {
    if (low >= high) return;

    if (high - low == 1) {
        if (arr[high] < arr[low]) std::swap(arr[low], arr[high]);
        return;
    }

    if (high - low == 2) {
        apply_three_element_rule(arr, low, high);
        return;
    }

    int mid = low + (high - low) / 2;
    if (arr[mid] < arr[low])  std::swap(arr[low], arr[mid]);
    if (arr[high] < arr[low]) std::swap(arr[low], arr[high]);
    if (arr[high] < arr[mid]) std::swap(arr[mid], arr[high]);

    int pivot = arr[mid];
    std::swap(arr[mid], arr[high]);

    constexpr size_t BLOCK_SIZE = 64;
    int left_offsets[BLOCK_SIZE];
    int right_offsets[BLOCK_SIZE];

    int i = low;
    int j = high - 1;

    int num_left = 0, num_right = 0;
    int idx_l = 0, idx_r = 0;
    int start_l = 0, start_r = 0;

    while (true) {
        if (num_left == 0) {
            if (i > j) break;
            start_l = i;
            int block = std::min<int>(BLOCK_SIZE, j - i + 1);
            for (int k = 0; k < block; ++k) {
                left_offsets[num_left] = k;
                num_left += (arr[i + k] >= pivot);
            }
            i += block;
            idx_l = 0;
        }

        if (num_right == 0) {
            if (i > j) break;
            int block = std::min<int>(BLOCK_SIZE, j - i + 1);
            start_r = j - block + 1;
            for (int k = block - 1; k >= 0; --k) {
                right_offsets[num_right] = k;
                num_right += (arr[start_r + k] < pivot);
            }
            j -= block;
            idx_r = 0;
        }

        int min_swaps = std::min(num_left, num_right);
        for (int k = 0; k < min_swaps; ++k) {
            std::swap(arr[start_l + left_offsets[idx_l + k]],
                      arr[start_r + right_offsets[idx_r + k]]);
        }

        num_left -= min_swaps;
        num_right -= min_swaps;
        idx_l += min_swaps;
        idx_r += min_swaps;
    }

    int split;
    if (num_left > 0) {
        int last_less = i - 1;
        for (int k = num_left - 1; k >= 0; --k) {
            std::swap(arr[start_l + left_offsets[idx_l + k]], arr[last_less]);
            last_less--;
        }
        split = last_less + 1;
    } else if (num_right > 0) {
        int first_greater = j + 1;
        for (int k = num_right - 1; k >= 0; --k) {
            std::swap(arr[start_r + right_offsets[idx_r + k]], arr[first_greater]);
            first_greater++;
        }
        split = first_greater;
    } else {
        split = i;
    }

    std::swap(arr[split], arr[high]);

    blockQuicksortModified(arr, low, split - 1);
    blockQuicksortModified(arr, split + 1, high);
}


// Benchmark Runner

int main() {
    const size_t ARRAY_SIZE = 1000000;
    const size_t NUM_TRIALS = 100;

    std::mt19937 rng(1337);
    std::uniform_int_distribution<int> dist(1, 1000000);

    double total_time_unmodified = 0.0;
    double total_time_modified = 0.0;

    std::cout << "Starting benchmark...\n";
    std::cout << "Array Size: " << ARRAY_SIZE << "\n";
    std::cout << "Trials:     " << NUM_TRIALS << "\n\n";

    for (size_t trial = 1; trial <= NUM_TRIALS; ++trial) {
        std::vector<int> original(ARRAY_SIZE);
        for (size_t i = 0; i < ARRAY_SIZE; ++i) {
            original[i] = dist(rng);
        }

        std::vector<int> vec1 = original;
        std::vector<int> vec2 = original;

        double current_unmod_time = 0.0;
        double current_mod_time = 0.0;

        // Alternate execution order to mitigate CPU cache effects
        if (trial % 2 != 0) {
            // Run Modified First
            auto start2 = std::chrono::steady_clock::now();
            blockQuicksortModified(vec2, 0, vec2.size() - 1);
            auto end2 = std::chrono::steady_clock::now();
            current_mod_time = std::chrono::duration<double, std::milli>(end2 - start2).count();

            // Run Unmodified Second
            auto start1 = std::chrono::steady_clock::now();
            blockQuicksortUnmodified(vec1, 0, vec1.size() - 1);
            auto end1 = std::chrono::steady_clock::now();
            current_unmod_time = std::chrono::duration<double, std::milli>(end1 - start1).count();
        } else {
            // Run Unmodified First
            auto start1 = std::chrono::steady_clock::now();
            blockQuicksortUnmodified(vec1, 0, vec1.size() - 1);
            auto end1 = std::chrono::steady_clock::now();
            current_unmod_time = std::chrono::duration<double, std::milli>(end1 - start1).count();

            // Run Modified Second
            auto start2 = std::chrono::steady_clock::now();
            blockQuicksortModified(vec2, 0, vec2.size() - 1);
            auto end2 = std::chrono::steady_clock::now();
            current_mod_time = std::chrono::duration<double, std::milli>(end2 - start2).count();
        }

        total_time_unmodified += current_unmod_time;
        total_time_modified += current_mod_time;

        std::cout << "Trial " << std::setw(2) << trial
                  << " - Unmodified: " << std::fixed << std::setprecision(2) << current_unmod_time << " ms"
                  << " | Modified: " << current_mod_time << " ms"
                  << " (Order: " << (trial % 2 != 0 ? "Mod First" : "Unmod First") << ")\n";
    }

    double avg_unmod = total_time_unmodified / NUM_TRIALS;
    double avg_mod = total_time_modified / NUM_TRIALS;

    // Calculate percentage difference relative to the unmodified version
    double percent_diff = ((avg_unmod - avg_mod) / avg_unmod) * 100.0;

    std::cout << "\n=== FINAL RESULTS ===\n";
    std::cout << "Average Time (Unmodified): " << std::fixed << std::setprecision(2) << avg_unmod << " ms\n";
    std::cout << "Average Time (Modified):   " << avg_mod << " ms\n";

    std::cout << "Performance Difference:    ";
    if (percent_diff > 0) {
        std::cout << "Modified is " << percent_diff << "% FASTER than Unmodified\n";
    } else if (percent_diff < 0) {
        std::cout << "Modified is " << std::abs(percent_diff) << "% SLOWER than Unmodified\n";
    } else {
        std::cout << "Both versions performed exactly the same\n";
    }

    return 0;
}