stooge_sort.cpp

// C++ program to implement Stooge  Sort
/*
The function of the stooge sort function is to check if the value at index 0 is 
greater than the value at last index, if YES then to swap those values.
Call the Stooge sort function recursively on initial 2/3rd of the array, last 2/3rd
and again initial 2/3rd to get the given array sorted
*/
#include <bits/stdc++.h>
using namespace std;

void stooge_sort(int arr[], int start, int end)
{
    // If the value at last index is smaller than the value at index 0, Swap them.
    if (arr[start] > arr[end])
        swap(arr[start], arr[end]);

    // For finding the first and last two by third elements in the array
    if (end - start + 1 > 2)
    {
        int twobythird = (end - start + 1) / 3;

        //Recursively call the function on the initial two by third, last two by third followed by the initial two by third
        if ((end - twobythird) >= start)
            stooge_sort(arr, start, end - twobythird);
        if (end >= (start + twobythird))
            stooge_sort(arr, start + twobythird, end);
        if ((end - twobythird) >= start)
            stooge_sort(arr, start, end - twobythird);
    }
}

int main()
{
    int n;
    cout << "\nHow many numbers do you want to sort? ";
    cin >> n;
    int arr[n];

    if (n <= 0)
    {
        cout << "There are no numbers to sort!!!";
        return 0;
    }
    // Input the numbers to sort
    cout << "Enter the numbers: ";
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    //Call the sort function
    stooge_sort(arr, 0, n - 1);

    cout << "The numbers in sorted order is: ";
    // Print the sorted array
    for (int i = 0; i < n; i++)
        cout << arr[i];
    cout << endl;

    return 0;
}

/*
Time Complexity: O(n^2), generally slower than bubble sort
Space Complexity: O(n)

SAMPLE INPUT AND OUTPUT

SAMPLE 1
How many numbers do you want to sort? 5
Enter the numbers: 1 3 5 2 4
The numbers in sorted order is:  1  2  3  4  5

SAMPLE 2
How many numbers do you want to sort? 0
There are no numbers to sort!!!
*/