Parallel Merge Sort

["R. Stegers" <rstegers@cs.vu.nl>]

I want to create a generic package which can sort an array with any type of
elements. The index is of the integer type. It is also required that the
merge sort is performed in parallel. I'm a C/C++-programmer with very
limited Ada experience. I think I got the idea of tasks/rendevous right. I
run into some problems here:

 - How can I dynamicaly allocate a temporary array (for which i don't know
the size in advance?) It seems inpossible to me.
 - How to create tasks from within a task: The subTask1 en subTask2
declarations generate errors: "Task type cannot be used as type mark within
its own body"

I hope someone can give me a hint. The code is below.

Thanks in advance,

Ruud



So far I created this definition and body (with some pseudo code):

*** SORT_PACKAGE.ADS ***
generic
  type element_type is private;
  with function "<=" (element1, element2 : element_type) return Boolean;
package SORT_PACKAGE is

  type element_array is array(integer range <>) of element_type;

  procedure Sort(InArray : in out element_array);

  task type mergeSortTask is
    entry doSort(InArray : in out element_array);
    entry awaitResult;
  end mergeSortTask;

end SORT_PACKAGE;


*** SORT_PACKAGE.ADB ***
with SORT_PACKAGE;

package body SORT_PACKAGE is

  procedure Sort(InArray : in out element_array) is
     baseTask : MergSortTask;
  begin
     baseTask.doSort(InArray);
  end Sort;

  task body MergeSortTask is
    subTask1 : MergeSortTask;
    subTask2 : MergeSortTask;
  begin

    accept doSort(InArray : in out element_array) do
      ** How to get the InArray to be used outside the doSort?? **
      -- Synchronize with the caller but return control
    end doSort;

    if (**array size > 1 element**)
      -- Actually sort the array here
      subTask1.doSort(**<1st half>**);
      subTask2.doSort(**<2nd half>**);

      -- Wait till both sub-task have finished sorting
      subTask1.awaitResult;
      subTask2.awaitResult;

      -- Merge both halfs here
      **...**
    endif

    accept awaitResult do
      -- When this point is reached, the work is done
    end awaitResult;

  end mergeSortTask;

end SORT_PACKAGE;