Custom Stride Insertion Sort vs Standard Knuth Shell Sort vs Custom Insertion vs Standard Insertion

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

// Benchmark: Custom Stride Insertion Sort vs Standard Knuth Shell Sort vs Custom Insertion vs Standard Insertion
// Contact Email [email protected]
// Created by I.A

// 1. Standard Insertion Sort
void standardInsertionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

// 2. Custom Jump Insertion Sort
void customJumpSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            if (j >= 1) {
                arr[j + 1] = arr[j];
                if (arr[j - 1] > key) {
                    arr[j] = arr[j - 1];
                    j -= 2;
                } else {
                    arr[j] = key;
                    goto placed;
                }
            } else {
                arr[j + 1] = arr[j];
                j--;
            }
        }
        arr[j + 1] = key;
        placed:;
    }
}

// 3. Custom Stride Insertion Sort
void strideInsertionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 16;

        // Step backward by 16
        while (j >= 0 && arr[j] > key) {
            // Shift the 16 elements ahead by one position
            arr[j + 16] = arr[j + 15];
            arr[j + 15] = arr[j + 14];
            arr[j + 14] = arr[j + 13];
            arr[j + 13] = arr[j + 12];
            arr[j + 12] = arr[j + 11];
            arr[j + 11] = arr[j + 10];
            arr[j + 10] = arr[j + 9];
            arr[j + 9]  = arr[j + 8];
            arr[j + 8]  = arr[j + 7];
            arr[j + 7]  = arr[j + 6];
            arr[j + 6]  = arr[j + 5];
            arr[j + 5]  = arr[j + 4];
            arr[j + 4]  = arr[j + 3];
            arr[j + 3]  = arr[j + 2];
            arr[j + 2]  = arr[j + 1];
            arr[j + 1]  = arr[j];
            j -= 16;
        }

        // Clean up the remaining 1 to 15 elements that weren't covered by the 16-stride
        int k = j + 15;
        while (k >= 0 && arr[k] > key) {
            arr[k + 1] = arr[k];
            k--;
        }
        arr[k + 1] = key;
    }
}

// 4. Standard Knuth Shell Sort
void shellSort(std::vector<int>& arr) {
    int n = arr.size();
    int h = 1;

    // 1. Calculate the largest gap in the 3k+1 sequence that is < n
    // Sequence: 1, 4, 13, 40, 121, 364, 1093...
    while (h < n / 3) {
        h = 3 * h + 1;
    }

    // 2. Start with the largest gap and reduce it down to 1
    while (h >= 1) {
        for (int i = h; i < n; i++) {
            int temp = arr[i];
            int j;
            // Standard gapped insertion sort
            for (j = i; j >= h && arr[j - h] > temp; j -= h) {
                arr[j] = arr[j - h];
            }
            arr[j] = temp;
        }
        // Move to the next smaller gap in the sequence
        h /= 3;
    }
}

int main() {
    const int NUM_ELEMENTS = 1000;
    const int NUM_TRIALS = 10000;

    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dist(1, 100000);

    double totalStd = 0, totalJump = 0, totalStride = 0, totalShell = 0;

    std::cout << "Benchmarking... please wait." << std::endl;

    for (int t = 0; t < NUM_TRIALS; ++t) {
        std::vector<int> source(NUM_ELEMENTS);
        for (int& x : source) x = dist(gen);

        std::vector<int> d1 = source, d2 = source, d3 = source, d4 = source;

        // Standard
        auto s1 = std::chrono::steady_clock::now();
        standardInsertionSort(d1);
        totalStd += std::chrono::duration<double>(std::chrono::steady_clock::now() - s1).count();

        // Jump
        auto s2 = std::chrono::steady_clock::now();
        customJumpSort(d2);
        totalJump += std::chrono::duration<double>(std::chrono::steady_clock::now() - s2).count();

        // Stride
        auto s3 = std::chrono::steady_clock::now();
        strideInsertionSort(d3);
        totalStride += std::chrono::duration<double>(std::chrono::steady_clock::now() - s3).count();

        // Shell
        auto s4 = std::chrono::steady_clock::now();
        shellSort(d4);
        totalShell += std::chrono::duration<double>(std::chrono::steady_clock::now() - s4).count();

        // Logic check
        if (!std::is_sorted(d2.begin(), d2.end()) || !std::is_sorted(d3.begin(), d3.end()) || !std::is_sorted(d4.begin(), d4.end())) {
            std::cout << "CRITICAL ERROR: A Sort Failed!" << std::endl;
            return 1;
        }
    }

    std::cout << "\n" << std::left << std::setw(25) << "Algorithm" << " | " << "Total Time (s)" << std::endl;
    std::cout << "------------------------------------------------" << std::endl;
    std::cout << std::setw(25) << "Standard Insertion" << " | " << std::fixed << std::setprecision(6) << totalStd << std::endl;
    std::cout << std::setw(25) << "Custom Jump Sort"   << " | " << std::fixed << std::setprecision(6) << totalJump << std::endl;
    std::cout << std::setw(25) << "Custom Stride Sort"        << " | " << std::fixed << std::setprecision(6) << totalStride << std::endl;
    std::cout << std::setw(25) << "Standard Knuth Shell Sort"         << " | " << std::fixed << std::setprecision(6) << totalShell << std::endl;

    return 0;
}