Example: Stooge Sort Algorithm in C++

// Stooge Sort Algorithm
#include <iostream>
#include <vector>
#include <algorithm> // Required for std::swap

// Function to print a vector
void printVector(const std::vector<int>& arr) {
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

// Function to implement Stooge Sort
void stoogeSort(std::vector<int>& arr, int l, int h) {
    // Step 1: Base Case - If the sub-array has one or zero elements, it's sorted.
    if (l >= h) {
        return;
    }

    // Step 2: Swap if the first element is greater than the last.
    // This ensures the largest element potentially moves to the right.
    if (arr[l] > arr[h]) {
        std::swap(arr[l], arr[h]);
    }

    // Step 3: If there are more than 2 elements in the sub-array,
    // apply recursion.
    if (h - l + 1 > 2) {
        // Calculate the size of 1/3 of the array
        // which determines the sub-array boundaries.
        int t = (h - l + 1) / 3;

        // Recursively sort the first 2/3 of the array
        stoogeSort(arr, l, h - t);

        // Recursively sort the last 2/3 of the array
        stoogeSort(arr, l + t, h);

        // Recursively sort the first 2/3 again
        // This is the unique and crucial step that distinguishes Stooge Sort.
        stoogeSort(arr, l, h - t);
    }
}

int main() {
    // Step 1: Initialize an unsorted vector of integers.
    std::vector<int> arr = {4, 2, 7, 1, 3, 9, 5, 8, 6};

    // Step 2: Print the original array to show its unsorted state.
    std::cout << "Original array: ";
    printVector(arr);

    // Step 3: Call the stoogeSort function to sort the array.
    // The sorting process will happen in-place within the vector.
    stoogeSort(arr, 0, arr.size() - 1);

    // Step 4: Print the sorted array to verify the algorithm's output.
    std::cout << "Sorted array:   ";
    printVector(arr);

    // Step 5: Test with another array
    std::vector<int> arr2 = {10, -5, 0, 20, 15};
    std::cout << "\nOriginal array 2: ";
    printVector(arr2);
    stoogeSort(arr2, 0, arr2.size() - 1);
    std::cout << "Sorted array 2:   ";
    printVector(arr2);

    return 0;
}