C++ merge sort реализация

Question

Я хочу реализовать сортировку слияния с C++ и вектором (учитывая количество входных чисел целых чисел неизвестно). Я попытался реализовать на основе идеи реализации Bottom-up через википедию: http://en.wikipedia.org/wiki/Merge_sort. Я вышел со следующим кодом. Он может передавать компиляцию, но умирает при вводе чисел. Я не знаю, что здесь происходит.

#include<iostream> 
#include<vector> 
using namespace std; 

void BottomUpMerge(vector<int>, vector<int>::iterator, vector<int>::iterator, vector<int>::iterator, vector<int>); 

void BottomUpSort(int n, vector<int> A, vector<int> B) 
{ 
    int width; 

    /* Each 1-element run in A is already "sorted". */ 

    /* Make successively longer sorted runs of length 2, 4, 8, 16... until whole array is sorted. */ 
    for (width = 1; width < n; width = 2 * width){ 
    vector<int>::iterator leftstart; 

    /* Array A is full of runs of length width. */ 
    for (leftstart = A.begin(); leftstart <= A.end(); leftstart = leftstart + 2 * width){ 
     /* Merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[] */ 
     /* or copy A[i:n-1] to B[] (if(i+width >= n)) */ 
     vector<int>::iterator rightstart; 
     vector<int>::iterator rightend; 
     if(leftstart+width >= A.end()){ 
      rightstart = A.end(); 
     } 
     else{ 
      rightstart = leftstart+width; 
     } 
     if(leftstart+2*width >= A.end()){ 
      rightend = A.end(); 
     } 
     else{ 
      rightend = leftstart+2*width; 
     } 

     BottomUpMerge(A, leftstart, rightstart, rightend, B); 
    } 

    /* Now work array B is full of runs of length 2*width. */ 
    /* Copy array B to array A for next iteration. */ 
    /* A more efficient implementation would swap the roles of A and B */ 
    A = B; 
    /* Now array A is full of runs of length 2*width. */ 
    } 
} 

void BottomUpMerge(vector<int> A, vector<int>::iterator iLeft, vector<int>::iterator iRight, vector<int>::iterator iEnd, vector<int> B) 
{ 
    vector<int>::iterator i0 = iLeft; 
    vector<int>::iterator i1 = iRight; 
    vector<int>::iterator j = B.begin() + distance(iLeft, A.begin()); //iterator for vector B 

    /* While there are elements in the left or right lists */ 
    for (; j != B.end(); j++){ 
    /* If left list head exists and is <= existing right list head */ 
    if (i0 < iRight && (i1 >= iEnd || *i0 <= *i1)){ 
     *j = *i0; 
     i0 = i0 + 1; 
    } 
    else{ 
     *j = *i1; 
     i1 = i1 + 1; 
    } 
    } 
} 


int main(){ 
    int input; 
    vector<int> numbers; //input vector of numbers 

    cout << "Please input the numbers to be sorted:" << endl; 
    while(cin>>input){ 
     numbers.push_back(input); 
    } 

    int length = numbers.size(); 
    vector<int> sorted = numbers; //work vector ensure has the same size of the original vector 

    BottomUpSort(length, numbers, sorted); 

    vector<int>::iterator it; 
    for(it = numbers.begin(); it != numbers.end(); ++it) { 
     std::cout << (*it) << '\n'; 
    } 

    system("pause"); 
    return 1; 
} 

Answer 1

Посмотрите здесь:

BottomUpMerge(A, leftstart, rightstart, rightend, B); 
... 

void BottomUpMerge(vector<int> A, vector<int>::iterator iLeft, ...) 
{ 
    ... 

Вы передаете векторы по значению, что означает, что BottomUpMerge обрабатывает копии из них. Но итераторы все еще указывают на оригиналы, и наступает веселье. Передавайте векторы по ссылке, и по крайней мере некоторые из этих проблем должны исчезнуть.

(Вы должны обнаружили это, когда вы были протестировать эту функцию, прежде чем вы написали все окружающие кода. Никогда не добавляйте код, который не работает.)