sorting - MIPS 归并排序递归

Question

我需要为合并排序编写 MIPS 汇编语言代码。我已经创建了合并函数，但是使用递归的 merge_sort 函数让我很困惑。我已经发布了相同的参考 C 代码。我知道必须使用堆栈，但是，作为初学者自己无法做到这一点，我将不胜感激。

int merge_sort(int arr[],int low,int high)
{
  int mid;
  if(low<high) {
mid=(low+high)/2;
// Divide and Conquer
merge_sort(arr,low,mid);
merge_sort(arr,mid+1,high);
// Combine
merge(arr,low,mid,high);
 }

 return 0;
}

Answer 1

为什么不从下往上走，第一merge对单例，然后是已经排序的 2 长度子数组对，然后是 4 长度子数组对，等等，log n在一个循环中通过同一个数组？

剩下的问题是实施merge。它将被重复调用，但不会递归调用。这merge当然必须将其输出写回到输入区域上的数组中，也许制作其输入的临时副本以进行处理。

void mrgsort( int a[], int n) // pseudo-code
{
    if( n < 1 ) return;
    int s1 = 1, s2 = 2;
    do
    {
        int i, k = n/s2, p1=0, p2=s1;
        for( i=0; i<k; ++i, p1+=s2, p2+=s2 )
        {
            merge(p1, p2); // merge chunks of size s1
        }
        //  deal with the edge ...
        if( i > 0 )
        {
            if( p2 < n ) merge_edge(p1,p2,n); // 2nd chunk shorter
        }
        s1 = s2;
        s2 = s2*2;
    } while( s2 <= n )
    if( s1 < n )
        merge_edge(0,s1,n);                   // 2nd chunk shorter
}

没有递归，只有一个循环。