text: /*************************************************************************
  > File Name: slow_sort.cpp
  > Author: yoghourt->ilvcr 
  > Mail: liyaoliu@foxmail.com  @@  ilvcr@outlook.com 
  > Created Time: 2018年07月26日 星期四 22时56分36秒
  > Description: 
      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];
          a[j] = a[m];
          a[m] = temp;
      }
      SlowSort(a, i, j-1);
  }
  
  //Sample Main function
  int main(int argc, char* argv[]){
  
      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;
  }
  
  
  