In a message dated 04-21-98, Dominic Battre said to David Noon about
Mergesort (was Quicksort,
Hi Dominic,
DB>As you seem to like sort-algorithms here I've got straight 
DB>2-way mergesort for you.
Thanks.
DB>Could you test my mergesort-algorithms, too?
Certainly. I also collected your Natural Mergesort template from the other
message.
DB>I know that they are O(N log N) but I don't know how fast they really
DB>are.
First, we need to get the code to work.
DB>template  void ascending(T array[], int l, int r) {
DB>  int i, j, k, m;
DB>  T array2[maxSize];
You have a problem right here. The array2[] holding area should not be
allocated afresh on each recursion. It needs to be allocated just once at
the start of the sort.
Two thread-safe solutions spring immediately to mind:
 i) Pass an array from the calling routine, and if it is NULL use new to
    allocate enough memory. Pass it on during recursion. You will need to
    figure out when to delete it; a bool in local storage will do for this.
ii) Put a wrapper function around the recursive one, allocate the array in
    there, and delete it when the recursive function finally returns.
Also, using a fixed size for array2[] rather limits the sort routine. I
think the allocation should really be
    T * array2 = new T[r-l+1];
with a corresponding
    delete [] array2;
when the sort is finished.
Regards
Dave

___
 * MR/2 2.25 #353 * Vegetarian (n): Indian word for "lousy hunter".
--- Maximus/2 3.01
---------------