Re: [HELP]:Non-recursive merge sort

[Hung Quang Ngo <hngo@cs.umn.edu>]

 Hi ba'c Linh, non-recursive merge sort source code is included below
 It's written in C, and thus can be easily converted into Pascal :-)

 Best Regards,
 Hu+ng
--------------------------------------------------------------
If we knew what it was we were doing, it would not be called 
research, would it ?
                                              --Albert Eistein 
--------------------------------------------------------------

void MergeSort(ElementType *A, int N)
{
   ElementType *Target, *Tmp;
   int L, K, targetIndex, size;

   Target = (ElementType *)malloc(sizeof(ElementType) * N);
   if (Target == NULL)
   {
      perror("Out of memory.\n");
      exit(1);
   }

   for (size = 1; size < N; size *= 2)
   {
      for (targetIndex = 0, lowIndex = 0; lowIndex < (N-1);
        lowIndex += size * 2, targetIndex += size * 2)
      {
         highIndex = lowIndex + size;
         if (highIndex > (N-1))
         {
            while (lowIndex <= (N-1))
            {
               Target[targetIndex] = A[lowIndex];
               targetIndex++;
               lowIndex++;
            }
         }
         else
         {
            if ((highIndex + size) > (N-1))
               Merge(A, lowIndex, highIndex, highIndex, (N-1), Target,
                 targetIndex);
            else
               Merge(A, lowIndex, highIndex, highIndex, 
                (highIndex + size), Target, targetIndex);
         } 
      }
      
      /* Swap Array and Target pointers */

      Tmp = A;
      A = Target;
      Target = Tmp;
   }
}

void Merge(ElementType A[], int index1, int end1, int index2, int end2,
  ElementType Target[], int index3)
{
   while (index1 < end1 && index2 < end2)
   {
      if (A[index1] <= A[index2])
      {
         Target[index3] = A[index1];
         index1++;
      }
      else
      {
         Target[index3] = A[index2];
         index2++;
      }
      index3++;
   }

   while (index1 < end1)
   {
      Target[index3] = A[index1];
      index1++;
      index3++;
   }

   while (index2 < end2)
   {
      Target[index3] = A[index2];
      index2++;
      index3++;
   }
}