Example: Stooge Sort Implementation in C

// Stooge Sort Implementation
#include <stdio.h>

// Function to swap two elements
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Function to implement Stooge Sort
// arr: The array to be sorted
// l: The starting index of the sub-array
// h: The ending index of the sub-array
void stoogeSort(int arr[], int l, int h) {
    // Base case: If the sub-array has one or zero elements, it's already sorted.
    if (l >= h) {
        return;
    }

    // Step 1: If the first element is greater than the last, swap them.
    // This ensures the smallest element isn't left at the very end.
    if (arr[l] > arr[h]) {
        swap(&arr[l], &arr[h]);
    }

    // Step 2: If there are more than two elements in the current sub-array,
    // apply the recursive Stooge Sort steps.
    if (h - l + 1 > 2) {
        // Calculate 't', which represents roughly one-third of the sub-array's length.
        // The length of the current sub-array is (h - l + 1).
        int t = (h - l + 1) / 3;

        // Step 2a: Recursively sort the first two-thirds of the elements.
        // This covers elements from 'l' up to 'h - t'.
        stoogeSort(arr, l, h - t);

        // Step 2b: Recursively sort the last two-thirds of the elements.
        // This covers elements from 'l + t' up to 'h'.
        stoogeSort(arr, l + t, h);

        // Step 2c: Recursively sort the first two-thirds of the elements again.
        // This is crucial for correcting any elements that might have been
        // moved out of place by the second recursive call.
        stoogeSort(arr, l, h - t);
    }
}

int main() {
    // Step 1: Define an unsorted integer array.
    int arr[] = {4, 2, 8, 1, 5, 7, 3, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    // Step 2: Apply Stooge Sort to the entire array.
    // The initial call covers the array from index 0 to n-1.
    stoogeSort(arr, 0, n - 1);

    printf("Sorted array:   ");
    printArray(arr, n);

    return 0;
}