## C++, sort, slow_sort.cpp

// 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>

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;
std::cout << "\nEnter the number of elements : ";

std::cin >> size;

int *arr = new int[size];

std::cout << "\nEnter the unsorted elements : ";

for (int i = 0; i < size; ++i) {
std::cout << "\n";
std::cin >> arr[i];
}

SlowSort(arr, 0, size);

std::cout << "Sorted array\n";

for (int i = 0; i < size; ++i) {
std::cout << arr[i] << " ";
}

delete[] arr;
return 0;
}