c++ - 合并排序变体 : using link array

Question

我一直在寻找归并排序的变体。所以我的教科书说，

函数 Merge 的变体，其中根本不需要移动任何记录，可以通过使用辅助数组链接来实现。

首先，我想声明一下代码。

Algo MergeSort(low,high)
{

// a is the array to be sorted using auxiliary array link. 

if(high-low<15)
return InsertionSort1(a,link,low,high);

else
{

     mid = (low+high)/2;
    q=MergeSort(low,mid);
    r=MergeSort(mid+1,high);
    return Merge1(q,r);

}

}

// The function Merge1 is as defined:

function Merge1(q,r)
{

// q and r are pointers to list contained in the global array link[0:n], the lists pointed at by q //and r are merged and a pointer to the beginning of the merged list is returned.

    i=q;
    j=r;
    k=0;

while(i!=0 && j!=0) 
{ 
    if(a[i]<=a[j])
    {
          link[k]=i;
          k=i;
          i=link[i];
    }

    else
    {

           link[k]=j;
           k=j;
           j=link[j];
    }
} // end of while

if(i=0) 
  link[k]=j;

else
  link[k]=i;

return link[0];
}

好吧，我对算法的理解是:

1. 如果元素个数少于15个，应用插入排序对这些元素进行排序。
2. 这样，我们会得到很多列表，它们会自行排序，但整个数组不会这样排序。
3. 要对整个数组进行排序，使用函数Merge。

我的问题是，

Merge 函数如何将不同的排序列表合并为一个排序列表？我对 link 数组的概念一无所知。

很抱歉，我非常努力地去理解，但我不明白输出数组是如何“排序”的？

任何类型的例子都会有很大的帮助。谢谢。

Answer 1

我清理了代码，还添加了一个使用起始索引数组的自底向上版本(见下文)。我在 MergeSort() 中更改为 high 以结束，因此调用现在是 MergeSort(0, SIZE)。 i = MergeSort() 返回 a[] 中最小值的索引，然后 i = link[i] 是第 2 个元素，i = link[i] 是第 3 个元素，直到 i = -1。 MergeSort() 不使用插入排序，而是直接对 size==1 或 size==2 的组进行排序并初始化 link[]。

MergeLists() 使用 head 作为列表的开头(旧代码使用 link[0])，并使用 -1 作为列表的结尾(旧代码使用 0)。这允许将 a[0] 排序为 a[n-1](旧代码将 a[1] 排序为 a[n]，其中未使用 a[0])。

如果a[] ={5,4,8,7}，那么MergeSort()返回一个1，而link[] = {3,0,-1,2}, link[1] = 0, link [0] = 3, link[3] = 2, link[2] = -1, 所以顺序是a[1], a[0], a[3], a[2]。

#define SIZE 4
static unsigned int a[SIZE] = {5,8,4,7};
static size_t link[SIZE];               /* index to next element */

size_t MergeLists(size_t i, size_t j)
{
size_t head;
size_t *pprev = &head;                  /* ptr: head or link[] */
    while((i != -1) && (j != -1)){      /* while not end lists */
        if(a[i] <= a[j]){               /*   if i < j          */
            *pprev = i;                 /*      link to i      */
            pprev = &link[i];           /*      advance pprev  */
            i=*pprev;                   /*      advance i      */
        } else {                        /*   else              */
            *pprev = j;                 /*      link to j      */
            pprev = &link[j];           /*      advance pprev  */
            j=*pprev;                   /*      advance j      */
        }
    }
    if(i == -1)                         /* if end of i list    */
        *pprev=j;                       /*   link to rest of j */
    else                                /* else                */
        *pprev=i;                       /*   link to rest of i */
    return head;
}

size_t MergeSort(size_t low, size_t end)
{
size_t mid, i, j;
    if((end - low) == 0){               /* if size == 0           */
        return low;                     /*  (only on first call)  */
    }
    if((end - low) == 1){               /* if size == 1           */
        link[low] = -1;                 /*    initialize link[]   */
        return low;                     /*    return index        */
    }
    if((end - low) == 2){               /* if size == 2           */
        if(a[low] <= a[end-1]){         /*   if in order          */
            link[low]   = end-1;        /*    initialize link[]   */
            link[end-1] = -1;
            return low;                 /*    return index        */
        } else {                        /*   else                 */
            link[end-1] = low;          /*    initialize link[]   */
            link[low]   = -1;
            return end-1;               /*    return index        */
        }
    }
    mid = (low+end)/2;                  /* size > 2, recursively  */
    i = MergeSort(low, mid);            /*   split lists until    */
    j = MergeSort(mid, end);            /*   size <= 2            */
    return MergeLists(i, j);            /* merge a pair of lists  */
}

int main(void)
{
size_t i;
    i = MergeSort(0, SIZE);
    do{
        printf("%3d", a[i]);
        i = link[i];
    }while(i != -1);
    return 0;
}

这是一个非递归的例子。它使用一个起始索引数组 S[]。 N[] 与上面的 link[] 相同，而 MergeLists() 与之前相同。 S[0] 指向大小为 1 的列表，S[1] 指向大小为 2 的列表，S[2] 指向大小为 4 的列表，... S[i] 指向大小为 2^i (2为 i) 次方。 S[31] 指向无限大小的列表。元素一次一个地合并到数组中，然后数组列表合并形成一个列表。

#define NUMIDX (32)                     // number of indexes in array

// A[] is array to be sorted
// N[] is array of indexes to next index
// l is index of N[] to left  list
// r is index of N[] to right list
// returns starting index (l or r) for merged list

size_t MergeLists(int A[],  size_t N[], size_t l, size_t r)
{
size_t head;
size_t *pprev = &head;                  // ptr: head or N[]
    while((l != -1) && (r != -1)){      // while not end lists
        if(A[l] <= A[r]){               //   if l <= r
            *pprev = l;                 //      link to l
            pprev = &N[l];              //      advance pprev
            l=*pprev;                   //      advance l
        } else {                        //   else
            *pprev = r;                 //      link to r
            pprev = &N[r];              //      advance pprev
            r=*pprev;                   //      advance r
        }
    }
    if(l == -1)                         // if end of l list
        *pprev=r;                       //   link to rest of r
    else                                // else
        *pprev=l;                       //   link to rest of l
    return head;
}

// A[] is array to be sorted
// N[] is set to array of indexes to next index (-1 = end list)
// low is starting index of A[]
// end is ending index of A[] (1 past last)
// returns starting index of N[] for merged list
// S[] is array of starting indexes in N[]
// S[i] is starting index of list of size pow(2,i)

size_t MergeSort(int A[], size_t N[], size_t low, size_t end)
{
size_t S[NUMIDX];                       // array of starting indexes
size_t i,j;
    if((end - low) == 0){               // if size == 0
        return low;                     //  (only on first call)
    }
    for(i = 0; i < (end-low); i++)      // init N[]
        N[i] = -1;
    for(i = 0; i < NUMIDX; i++)         // init S[]
        S[i] = -1;
    for(j = low; j < end; j++){         // merge index lists into S[], N[]
        low = j;
        for(i = 0; (i < NUMIDX) && (S[i] != -1); i++){
            low = MergeLists(A, N, S[i], low);
            S[i] = -1;
        }
        if(i == NUMIDX)
            i--;
        S[i] = low;
    }
    low = -1;                           // merge S[] lists to one list in N[]
    for(i = 0; i < NUMIDX; i++)
        low = MergeLists(A, N, S[i], low);
    return low;
}