//Returns the sorted vector after performing SlowSort
//It is a sorting algorithm that is of humorous nature and not useful.
//It's based on the principle of multiply and surrender, a tongue-in-cheek joke of divide and conquer.
//It was published in 1986 by Andrei Broder and Jorge Stolfi in their paper Pessimal Algorithms and Simplexity Analysis.
//This algorithm multiplies a single problem into multiple subproblems
//It is interesting because it is provably the least efficient sorting algorithm that can be built asymptotically,
//and with the restriction that such an algorithm, while being slow, must still all the time be working towards a result.
#include <iostream>
using namespace std;
void SlowSort(int a[], int i, int j)
{
if (i >= j)
return;
int m = i + (j - i) / 2; //midpoint, implemented this way to avoid overflow
int temp;
SlowSort(a, i, m);
SlowSort(a, m + 1, j);
if (a[j] < a[m])
{
temp = a[j]; //swapping a[j] & a[m]
a[j] = a[m];
a[m] = temp;
}
SlowSort(a, i, j - 1);
}
//Sample Main function
int main()
{
int size;
cout << "\nEnter the number of elements : ";
cin >> size;
int arr[size];
cout << "\nEnter the unsorted elements : ";
for (int i = 0; i < size; ++i)
{
cout << "\n";
cin >> arr[i];
}
SlowSort(arr, 0, size);
cout << "Sorted array\n";
for (int i = 0; i < size; ++i)
{
cout << arr[i] << " ";
}
return 0;
}