Merge Sort - gebe ein neues Array zurück, anstatt das zusammengefügte Array in das Eingabearray zu kopieren

Question

Ich versuche eine sehr naive Version von Merge Sort zu implementieren (ohne Berücksichtigung aller Optimierungen für diesen Zweck), wo mein Ziel ist, eine neue Kopie zurückzugeben des zusammengeführten Arrays statt der herkömmlichen Methode, das Eingabearray durch Referenz zu übergeben und die zusammengeführten Elemente darin zu kopieren.

Zu diesem Zweck ist mein Code wie folgt:

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. Ich weiß, dass dieses Array von merge ein lokales Array ist, und ich bin die Rückkehr es daher mergesort was wiederum darauf zurück zu main. Bin ich falsch bei der Annahme, dass dies von nachfolgenden rekursiven Aufrufe nicht ein- und ausgeht?

2. Mein Testeingang für diesen Code ist {1,0,9}. Ich sollte {0,1,9} bekommen, aber ich bekomme 32767.

Was fehlt mir hier?

Answer 1

Zuerst für merge - Sie sollten const Verweise auf Argumente übergeben, sonst machen Sie zu viele unnötige Kopien. Außerdem erhalten Sie den Zugriff auf result, während Sie in leer erstellen und nach Index zugreifen. Und es ist keine gute Idee, int für den Index zu verwenden. So könnte vereinfachte Version sein:

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

oder Version, die näher an Ihre:

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

Die rekursive Aufrufe zu MergeSort nichts tun, weil intArr von Wert genommen wird (kopiert) und Sie nicht den Ergebniswert verwendet wird.

So etwas sollte funktionieren:

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

recresult = merge(newLeft, newRight); 

---

Wie Slava in den Kommentaren erwähnt, können Sie auch UB haben, wenn result Zugriff, weil seine size 0:

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

Sie sollten Rufen Sie std::vector::resize auf, bevor Sie auf die Elemente zugreifen, indem Sie operator[] verwenden.