MIPS合并排序递归

我需要编写用于合并排序的MIPS汇编语言代码。我已经创建了合并函数，但使用递归的merge_sort函数广泛地混淆了我。我已经发布了相同的参考C代码。我知道堆栈必须被使用，但是，无法自己做初学者，我会很感激任何帮助。MIPS合并排序递归

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

来源

2012-08-22 arbit14

你试过了什么？你可以将简单的非递归C函数转换成MIPS吗？ – 0605002

为什么不从底部向上和第一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 
}

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

来源

2012-08-22 13:40:54

我的确这么想过，但是在MIPS中实现它给了一点麻烦。是的，合并不是这里的问题，而是merge_sort（有递归部分）。合并逻辑很容易转换为汇编代码。 – arbit14

但它没有*是递归的。您只需循环扫描阵列，同时增加单位尺寸。 –

MIPS合并排序递归

回答

相关问题