/*
Josh Stone
CS 476
Lab 4
Dr. Zoppetti
/*

/**************************************************************************/
import std.stdio : writeln;
import std.range : iota;
import std.parallelism : parallel;
import std.algorithm, std.array, std.range, std.random, std.algorithm, core.thread, std.stdio;
import std.datetime;
/**************************************************************************/
//http://rosettacode.org/wiki/Sorting_algorithms/Merge_sort#D
T[]
mergeSorted(T)(in T[] D) {
    if (D.length < 2)
        return D.dup;
    return [D[0 .. $ / 2].mergeSorted, D[$ / 2 .. $].mergeSorted].nWayUnion.array;
}
/**************************************************************************/
void
ToString(int[] arr)
 {
   write("A[] =      [");
   int i = 0;
   if (arr.length == 0)
   {
   writeln("]");
   }
   while (i < arr.length)
  {
   write(arr[i]);
   ++i;
   if (i == arr.length)
   {
    writeln("]");
    break;
   }
   else
   {
   write(", ");
   }
  }
 }
/**************************************************************************/
void
parallelMergeSort (int [] array, int threads, int N)
{
   int [][] result;
   int numElemsPerThread = N / threads;
   int numTougherThreads = N % threads;

   ulong lbound = 0;
   ulong ubound = 0;
   foreach (i; iota(threads).parallel) {
   // The body of the foreach loop is executed in parallel for each i
   // writeln("core ", i, " processing ");
    if (i < numTougherThreads)
   {
    lbound = i*(numElemsPerThread+1);
    ubound = i*(numElemsPerThread+1)+(numElemsPerThread+1);

      if ((ubound <= N) && (lbound <= N))
      {
       result ~= array[lbound..ubound].mergeSorted;
      }
   }

    if (i >= numTougherThreads)
  {
    int scale = 0;
    if (numTougherThreads != 0)
{
    scale = numTougherThreads;
}
    lbound = i*numElemsPerThread+scale;
    ubound = i*numElemsPerThread+scale+numElemsPerThread;

      if ((ubound <= N) && (lbound <= N))
     {
      result ~= array[lbound..ubound].mergeSorted;
     }
  }
}
       nWayUnion(result);
      // writeln("Parallel MergeSort: ", nWayUnion(result));
       //writeln("");
}
/**************************************************************************/

void main()
 {
    //N >= 0
    write("Enter size N >= 0 ==> ");
    int N;
    readf(" %s", &N);
    //Threads > 0
    write("Enter threads > 0 ==> ");
    int threads;
    readf(" %s", &threads);

    //writeln("Threads = ", threads);
    //writeln("Size = ", N);
    int[] array;
    int counter;

    while (counter < N)
   {
    auto i = uniform(0, 100);
    array ~= i;
    // writeln("A[", counter, "]", " = ", array[counter]);
    ++counter;
   }
   // write("Original ");
  //  array.ToString;
  //  writeln("");

    array.parallelMergeSort(threads, N);

   // write("Serial MergeSort:   ");

   //array.mergeSorted;
   return;
}