Mergesort on Vectors не сортировка

Question

Я пытаюсь сделать merge-sort на векторы, но я не знаю, что такое моя ошибка. Я сделал тест на рабочем столе, и он работает нормально, но затем, когда я запускаю код, он не знает, почему он ничего не сортирует и заполняет вектор трэш.

Вот код:

#include<iostream> 
#include<vector> 

using namespace std; 


//los vectores se pasan por referencia 
void merge(vector<int>& v, int inicio, int medio, int fin){ 
    int primera_mitad = medio-inicio+1; //para el primer arreglo 
    int segunda_mitad = fin-medio;  //para el segundo arreglo 
    //copio a cada arreglo las mitades 
    vector<int> n1; 
    vector<int> n2; 
    int i,j,k; 
    for(i=0; i<primera_mitad; i++){ 
    n1.push_back(v[inicio+i]); 
    } 
    for(j = 0; j<segunda_mitad; j++){ 
    n2.push_back(v[medio+j+1]); 
    } 
    //Ahora realizo las comparaciones para volver a ingresar al vector completo los valores 
    //de las mitades en orden. 
    i=0; 
    j=0; 
    k=inicio; 
    while(i<n1.size() && j<n2.size()){ //Mientras hayan elementos por pasar en ambos subarreglos(subvector) 
    if(n1[i]<=n2[j]){ 
     v.insert(v.begin()+k, n1[i]); 
     i++; 
    } 
    else{ 
     v.insert(v.begin()+k, n2[j]); 
     j++; 
    } 
    k++; 
    } 
    //Puede darse el caso de que un subarreglo se vacíe mas rápido que otro, por lo que pasamos directamente 
    //los demás elementos 
    while(i<n1.size()){ 
    v.insert(v.begin()+k, n1[i]); 
    i++; 
    k++; 
    } 
    while(j<n2.size()){ 
    v.insert(v.begin()+k, n2[j]); 
    j++; 
    k++; 
    } 
} 

void merge_sort(vector<int>& v, int inicio, int fin){ 
    if(inicio<fin){ 
    int medio = ((fin+inicio)/2); 
    merge_sort(v, inicio, medio); 
    merge_sort(v, medio+1, fin); 
    merge(v, inicio, medio, fin); 
    } 
} 


void print(vector<int>& v){ 
    cout<<endl; 
    int tam = v.size(); 
    for(int i = 0; i<tam; i++){ 
    cout<<i+1<<".\t"<<v[i]<<"\n"; 
    } 
} 

int main() { 
    cout<<"----------------MERGE SORT----------------\n\n"; 
    cout<<"\nPlease, fill the vector: \n\n"; 
    int a; 
    bool response = true; 
    vector<int> v; 
    while(response){ 
     cout<<"\nEnter your number: "; 
     cin>>a; 
     v.push_back(a); 
     cout<<"Another?(1/0): "; 
     cin>>response; 
     cout<<endl; 
    } 
    int tam = v.size(); 
    merge_sort(v, 0, tam-1); 
    print(v); 
    return 0; 
} 

Например, когда я поставил это число в качестве входных данных:

1 4 10 5 6 

Программа дает мне этот выход:

1. 1 
2. 1 
3. 1 
4. 10 
5. 10 
6. 1 
7. 1 
8. 10 
9. 1 
10. 10 
11. 1 
12. 10 
13. 1 
14. 10 
15. 4 
16. 5 
17. 6 

Надеется, что вы Помоги мне. Благодарю.

Answer 1

Вместо того, чтобы копировать из списка в начале, просто отслеживайте, где вы находитесь, и выполните слияние в новый выходной список. Когда закончите, ЗАМЕНИТЕ старые значения с новыми. Не используйте v.insert(). v [IDX] = выход [idx2]

ИЛИ

Вы можете держать два входных списков, но вам все равно нужно заменить значение в списке. v [idx ++] = значение. idx должен начинаться в начале первого списка.

В любом случае вы можете подумать об использовании итераторов вместо индексов. Таким образом, вы можете избежать передачи вектора. Вам не нужен произвольный доступ к структуре для записи сортировки слияния. Он должен работать с std :: list. Вы можете перемещать элементы, используя ++ iter.