マージソートは2の累乗であるサイズを持つベクトルを返します。

Question

したがって、ベクトル上でマージソートを行うコードを作成しようとしています。しかし、私は現在、2の累乗ではないベクトルサイズのサイズを入力するたびに、最後のソートベクトルはそのサイズを2の最も近い累乗に丸めます。ベクトルのサイズが10に設定されている場合は8が返され、100の場合は64が返されます。なぜこれがわからないのですか？ - 要素素子の中央数あなたが正しいベクターを構築するとき、あなたはvector_sort.size（）を追加することでなければならない中間に等しい要素の数を追加する

#include <iostream> 
#include <stdlib.h>  /* srand, rand */ 
#include <time.h> /* time */ 
#include <vector> 
#include <assert.h> 
#include <iterator> 
#include <algorithm> 
#include <functional> 
using namespace std; 

vector<int> merge(vector<int> &left, vector<int> &right) { 
    vector <int> result; 
    while (left.size() > 0 && right.size()>0) { 
     if (left[0] <= right[0]) { 
      result.push_back(left[0]); 
      left.erase(left.begin()); 
     } 
     else { 
      result.push_back(right[0]); 
      right.erase(right.begin()); 
     } 
    } 
    if (left.size() > 0) { 
     result.insert(result.end(), left.begin(), left.end()); 
    } 
    if (right.size() > 0) { 
     result.insert(result.end(), right.begin(), right.end()); 
    } 
    return result; 
} 

vector <int> mergesort(vector <int> &vector_sort) { 
    int size_of = vector_sort.size()/2; 
    vector <int > left(size_of), right(size_of), result(vector_sort.size()); 
    if (vector_sort.size() <= 1) { 
     return vector_sort; 
    } 
    else { 
     int middle = vector_sort.size()/2; 
     int counter = middle; 
     int second_half = middle; 
     for (int i = 0; i < middle; i++) { 
      left[i] = vector_sort[i]; 
     } 
     for (int i = 0; i < middle; i++) { 
      right[i] = vector_sort[counter]; 
      counter++; 
     } 
     left = mergesort(left); 
     right = mergesort(right); 
     if (left.back() <= right[0]) { 
      left.insert(left.end(), right.begin(), right.end()); 
      return left; 
     } 
     result = merge(left, right); 
     return result; 
    } 
} 
int main() { 
    const int t=10; 
    vector<int> vector_no(t); 
    vector<int> empty(t); 
    for (int i = 0; i < t; i++) { 
     int hello = rand() % 100000 + 1; 
     vector_no[i] = hello; 
    } 
    int hello2 = 0; 
    for (int i = 0; i < vector_no.size(); i++) { 
     hello2++; //I am using this for loop here just to count the size of the vector without getting a stack overflow error 
    } 
    cout << hello2 << "\n"; 
    vector_no = mergesort(vector_no); 
    hello2 = 0; 
    for (int i = 0; i < vector_no.size(); i++) { 
     hello2++; //I am using this for loop here just to count the size of the vector without getting a stack overflow error 
    } 
    cout << hello2 << "\n"; 
} 

Answer 1

：ここにコードがあります。小数点以下は切り捨てられるので、奇数長のリストの最後の要素を削除します。ソートを0または1の要素にマージするので、結果は2の累乗になります。