Re: [HELP]:Non-recursive merge sort

[Thuy Linh <thuylinh@bigpond.com>]

Hi  ba'c Hu+ng va` ba'c Anh,

Ca'm o+n hai ba'c nhie^`u la('m, now em try to convert it  into DLX :-0).
Em nha^.n ddu+o+.c email cu?a hai ba'c in this morning, sau ddo' va`o
tru+o+`ng mo` ddu+o+.c half way ro^`i, co`n mo^.t half nu+~a la` finish
ca'i assignment na`y. Thank you very much.
Cheers,
Linh.

Hung Quang Ngo wrote:

>  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++;
>    }
> }