我的合併排序代碼有什麼問題，我找不出來了？

Question

我是編程新手。我最近剛開始學習算法。 我的代碼應該執行合併排序過程，但它有一些錯誤，雖然它構建正確。 我的代碼需要輸入，然後停止工作。 它顯示這樣的錯誤：

#include<iostream> 
    using namespace std; 
    #define size 10 
    class mergesort { 
    public: 
     mergesort(){} 
     void merge(int a[]) { 
      int mid = 5; 
      if (size < 2) return; 
      int left[size]; int right[size]; 
      for (int i = 0; i < mid; i++) { 
       left[i] = a[i]; 
     } 
      for (int j = mid; j < size-1; j++) { 
       right[j-mid] = a[j]; 
      } 
      merge(left); 
      merge(right); 
      sort(left, right, a, mid, size-mid); 
     } 

     void sort(int left[], int right[], int a[], int L, int R) { 
      int i = 0; int j = 0; int k = 0; 
      while (i < L && j < R) { 
       if (left[i] <= right[j]) 
       { 
        a[k] = left[i]; 
        k++; i++; 
       } 
       else if (right[j] < left[i]) { 
        a[k] = right[j]; 
        k++; j++; 
       } 
      } 
      while (i < L) { 
       a[k] = left[i]; 
       k++; i++; 
      } 
      while (i < R) { 
       a[k] = right[j]; 
       k++; j++; 
      } 
     } 
    }; 
    void main() { 
     mergesort m; 
     int a[size]; 
     cout << "Enter the elements:" << endl; 
     for (int i = 0; i < size; i++) { 
      cin >> a[size]; 
     } 
     m.merge(a); 
    } 

Answer 1

堆棧溢出錯誤是由於無限遞歸「循環」。

merge（）需要兩個參數。在這個例子中，我使用_alloca（）從堆棧中分配，因此不需要空閒。這隻適用於小到不能溢出堆棧的數組。另一種方法是使用malloc（）和free（）。

void merge(int a[], int lo, int hi) // hi is end == last + 1 
    { 
     if((hi - lo) < 2) 
      return; 
     int mid = (lo+hi)/2; 
     int *left = _alloca((mid - lo)*sizeof(int)); // alloc from stack 
     int *right = _alloca((hi - mid)*sizeof(int)); // alloc from stack 
     for (int i = lo; i < mid; i++) 
      left[i-lo] = a[i]; 
     for (int i = mid; i < hi; i++) 
      right[i-mid] = a[i]; 
     merge(left, lo, mid); 
     merge(right, mid, hi); 
     sort(left, right, a, mid-lo, hi-mid); 
     } 
    } 

最後，而在排序（）需要使用Ĵ，而不是我的：

 while (j < R) {    // use j here 
      a[k] = right[j]; 
      k++; j++; 
     } 

替代方法 - 使用一次性輔助函數來做第二陣列相同的一個時間分配size作爲[]，或許稱它爲b []，並在進行拆分和合並時使用與b []相同的索引作爲[]。 b []將作爲參數傳遞給merge（）和sort（），並將用來代替left []和right []。

名稱很混亂，merge（）實際上是一個「排序」，而sort（）實際上是一個「合併」。