C++ merge sort trouble

Question

Ich bin neu in C++ und habe versucht, einen Code für Merge-Sort zu entwickeln. Ich habe es mit einem Beispiel-Array der Größe 15 getestet, aber die Antwort, die der Code ausgegeben hat, stimmt nicht. Ich kann nicht verstehen, was falsch läuft. Hier ist mein Code:

#include <stdlib.h> 
#include <stdio.h> 
#include <iostream> 
#include <string> 
#include <fstream> 
#include <vector> 
#include <unistd.h> 
#include <cstdlib> 

using namespace std; 

//two arrays, input 
int initial[15] = {200,1,2,9,8,98,6,44,5,4,67,15,3,2,0}; 
//for output 
int fin[15]; 

void sort(int* ini, int left, int right, int m); 

//saperate the input in a recursion 
void devide(int* ini, int left, int right){ 
    int m; 

    if(left < right){ 
      m = (left + right)/2; 
      devide(ini, left, m); 
      devide(ini, m+1, right); 

      sort(ini, left, right, m); 
    } 
} 


//sorting 
void sort(int* ini, int left, int right, int m){ 

    //first half, start at the first element in the input array 
    int first_h = left; 

    //second half, start at the first element after the 
    // middle element in the input array 
    int second_h = m+1; 

    //index for output array 
    int out = left; 

    //comparing, if both half of array have element 
    while(first_h <= m && second_h <= right){ 

      //put the smaller in the the output array 
      if(initial[first_h] < initial[second_h]){ 
       fin[out] = initial[first_h]; 
       first_h++; 
      } 
      else{ 
       fin[out] = initial[second_h]; 
       second_h++; 

      } 
      out++; 
    } 

    //if one of half of input is empty, put the rest element into the 
    // output array 
    while(first_h <= m){ 
      fin[out] = initial[first_h]; 
      out++; 
     first_h++; 
    } 
    while(second_h <= right){ 
      fin[out] = initial[second_h]; 
      out++; 
      second_h++; 
    } 
} 

int main(){ 
    devide(initial, 0, 14); 

    for(int i =0; i<15; i++){ 
      cout<<fin[i]; 
      cout<<","; 
    } 
    return 0; 
} 

Der Ausgang der Einleitung [], der Finne ist [] ist:

5,4,67,15,3,2,0,200,1,2,9,8,98,6,44, 

Answer 1

So ein kleiner Fehler, die Sie nicht in Betracht nehmen ist, dass Sie Übergeben Zeiger-Array Ini, aber innerhalb der Methode, die Sie immer noch die Methode initial und eine weitere Sache ist, sollten Sie in einem temporären Array nehmen, die die sortierten Werte zu Ihrem Ini-Array zuweisen würde.

So soll Ihr Code so etwas wie diese

void sort(int* ini, int left, int right, int m){ 
    int first_h = left; 
    int second_h = m+1; 
    int out = left; 
    while(first_h <= m && second_h <= right){ 
      if(ini[first_h] < ini[second_h]){ 
       fin[out] = ini[first_h]; 
       first_h++; 
      } 
      else{ 
       fin[out] = ini[second_h]; 
       second_h++; 

      } 
      out++; 
    } 

    while(first_h <= m){ 
      fin[out] = ini[first_h]; 
      out++; 
     first_h++; 
    } 
    while(second_h <= right){ 
      fin[out] = ini[second_h]; 
      out++; 
      second_h++; 
    } 
    for(int i=left; i<out; i++) 
    { 
     ini[i] = fin[i]; 
    } 
} 

Hoffnung sieht dies besser zu verstehen, den Algorithmus hilft!