Stooge Sort.cpp

// Program of Stooge Sort in C++

// C++ code to implement stooge sort
#include <iostream>
using namespace std;

// Function to implement stooge sort
void stoogesort(int arr[], int l, int h)
{
	if (l >= h)
		return;

	// If first element is smaller than last,
	// swap them
	if (arr[l] > arr[h])
		swap(arr[l], arr[h]);

	// If there are more than 2 elements in
	// the array
	if (h - l + 1 > 2) {
		int t = (h - l + 1) / 3;

		// Recursively sort first 2/3 elements
		stoogesort(arr, l, h - t);

		// Recursively sort last 2/3 elements
		stoogesort(arr, l + t, h);

		// Recursively sort first 2/3 elements
		// again to confirm
		stoogesort(arr, l, h - t);
	}
}

// Driver Code
int main()
{
	int arr[] = { 2, 4, 5, 3, 1 };
	int n = sizeof(arr) / sizeof(arr[0]);

	// Calling Stooge Sort function to sort
	// the array
	stoogesort(arr, 0, n - 1);

	// Display the sorted array
	for (int i = 0; i < n; i++)
		cout << arr[i] << " ";

	return 0;
}