マージソート - マージされた配列を入力配列にコピーするのではなく、新しい配列を返す

Question

私は、マージソート（この目的のためのすべての最適化を考慮していない）を非常に素朴なバージョンで実装しようとしています。入力配列を参照で渡し、結合された要素をその中にコピーする従来の方法ではなく、結合された配列の

そのためには、私のコードは以下の通りです：

vector<int> merge(vector<int> left, vector<int> right) 
{ 
    vector<int> result; 
    int leftIdx = 0; 
    int rightIdx = 0; 
    int resultIdx = 0; 

    while (leftIdx < left.size() && rightIdx < right.size()) { 
     if (left[leftIdx] < right[rightIdx]) { 
      result[resultIdx++] = left[leftIdx++]; 
     } else { 
      result[resultIdx++] = right[rightIdx++]; 
     } 
    } 

    while (leftIdx < left.size()) { 
     result[resultIdx++] = left[leftIdx++]; 
    } 

    while (rightIdx < right.size()) { 
     result[resultIdx++] = right[rightIdx++]; 
    } 

    return result; 
} 

vector<int> MergeSort(vector<int> intArr) 
{ 
    vector<int> recresult; 

    // base - if array is of length 1, nothing to do, return it as is 
    if (intArr.size() == 1) { 
     return intArr; 
    } else { 
     int mid = intArr.size()/2; 
     // copy left half 
     vector<int> leftArr(intArr.begin(), intArr.begin() + mid); 
     // copy right half 
     vector<int> rightArr(intArr.begin() + mid, intArr.end()); 

     MergeSort(leftArr); 
     MergeSort(rightArr); 

     recresult = merge(leftArr, rightArr); 
    } 

    return recresult; 
} 

1. 私はマージからこの配列は、ローカル配列であることを知っているので、私は順番にそれを返すなるマージソートするためにそれを返しますよメインに。 これは、それ以降の再帰呼び出しの との間でやりとりされていないと仮定して間違っていますか？

2. このコードへの入力は{1,0,9}です。私は{0,1,9}になるはずですが、私は32767を得ます。

私はここで何が欠けていますか？

Answer 1

最初にmerge - const参照を引数に渡す必要があります。そうしないと、不要なコピーが多すぎます。空の状態で作成し、インデックスでアクセスすると、resultにアクセスできなくなります。インデックスとしてintを使用することはお勧めできません。だから、単純化されたバージョンは次のようになります。近いご

vector<int> merge(const vector<int> &left, const vector<int> &right) 
{ 
    vector<int> result; 
    auto lit = left.begin(); 
    auto rit = right.begin(); 
    while(lit != left.end() || rit != right.end()) { 
     bool lft = false; 
     if(rit == right.end()) 
      lft = true; 
     else { 
      if(lit != left.end()) 
       lft = *lit < *rit; 
     } 
     result.push_back(lft ? *lit++ : *rit++); 
    } 
    return result; 
} 

またはバージョン：

vector<int> merge(const vector<int> &left, const vector<int> &right) 
{ 
    vector<int> result(left.size() + right.size()); 
    auto rst = result.begin(); 
    auto lit = left.begin(); 
    auto rit = right.begin(); 
    while(lit != left.end() && rit != right.end()) 
     *rst++ = *lit < *rit ? *lit++ : *rit++; 

    std::copy(lit, left.end(), rst); 
    std::copy(rit, right.end(), rst); 
    return result; 
} 

Answer 2

intArrは値（コピー）になり、結果値を使用していないため、MergeSortへの再帰呼び出しは何も行いません。

このような何かが動作するはず

：

auto newLeft = MergeSort(leftArr); 
auto newRight = MergeSort(rightArr); 

recresult = merge(newLeft, newRight); 

---

スラバはコメントで述べたようにresultにアクセスしたときにそのsizeが0であるので、あなたはまた、UBを持っている：

vector<int> result; // size = 0 
// ... 
result[resultIdx++] = left[leftIdx++]; // UB! 

あなたはすべきですoperator[]を使用して要素にアクセスする前にstd::vector::resizeを呼び出します。