//@Description Sketch of a merge sort implementation.
/**
 * This example provides a nice case study of the use of generators to produce 
 * complicated expressions. The generator exprBoolG is a high-order generator that
 * takes as a parameter a generator that produces operands, and generates an expression involving 
 * conjunctions and disjunctions of comparisons of those operands.  
 * 
 * 
 */

include "generators.skh";
pragma options "--bnd-inline-amnt 3 --bnd-inbits 3"; 
   

int[N] sort(int N, int[N] input){
   int[N] output=input;
   int[N] done = 0;
   int k=0;
   for(int i=0; i<N; ++i){
      for(int j=i+1; j<N; ++j){
         if( output[j]< output[i]){
            int tmp = output[j];
            output[j] = output[i];
            output[i] = tmp;
         }
      }
   }
   return output;
}



int[N] MergeSort(int N, int[N] input)implements sort{
   int[N] output=0;
   if(N>1){ 
      int No2a = N/2; int No2b = N-No2a;      
      int[No2a] firstHalf = input[0::No2a];
      int[No2b] secondHalf = input[No2a::No2b];
      firstHalf = MergeSort(No2a, firstHalf);
      secondHalf = MergeSort(No2b, secondHalf);
      int x=0;
      int y=0;      
      generator int chose(ref int choice){
         choice = ??;
         if(choice==0){ return firstHalf[x]; }
         if(choice==1){ return secondHalf[y]; }
         if(choice==2){ return N; }
         if(choice==3){ return No2a; }
         if(choice==4){ return No2b; }
         if(choice==5){ return x; }
         if(choice==6){ return y; }
         assert choice ≤6;
      }
      for(int i=0; i<N; ++i){         
         if(exprBoolG(chose, 0, {})){
            output[i] = firstHalf[x]; x = x+1;
         }else{
            output[i] = secondHalf[y]; y = y+1;
         }
      }
   }else{
      output = input;   
   }
   return output;
}