Основная функция пропуска?

Question

Я пытаюсь научить себя основам алгоритмов и структур данных через бесплатный онлайн-курс, и как таковой, хотя я бы дал ему первый выстрел в сортировке слияния. На самом деле это не будет использоваться ни для чего, так что это довольно неряшливо, но у меня, похоже, проблема, когда main не вызывает функцию MergeSort.

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

Любые мысли? Мне что-то не хватает?

#include <iostream> 
using namespace std; 

int *MergeSort(int array[], int sizeOf); 

int main(){ 
    int numbers[8] = {5, 4, 1, 8, 7, 2, 6, 3}; 

    int *array = MergeSort(numbers, 8); 

    for (int i = 0; i < 8; i++) 
     cout << array[i]; 

return 0; 

} 

int *MergeSort(int array[], int sizeOf){ 

    int *leftArr = new int[sizeOf/2];  // Build arrays to split in half 
    int *rightArr = new int[sizeOf/2]; 

    if (sizeOf < 2){          // Base case to end recursion 
     return array; 
    } 

    else{ 

     for (int i = 0; i < (sizeOf/2); i++){ // Left gets first half 
      leftArr[i] = array[i]; 
     } 

     int j = (sizeOf/2) - 1;       // Set point to start building 2nd 

     for (int i = sizeOf; i >= (sizeOf/2); i--){ 
      rightArr[j] = array[i];      // Build other half of array 
      j--; 
     } 

     leftArr = MergeSort(leftArr, sizeOf/2);   // Call Recursive functions 
     rightArr = MergeSort(rightArr, sizeOf/2); 

    } 

    static int *newArray = new int[sizeOf];  // Sorted array to Build 
    int k = 0;             // Iterators to build sorted func 
    int m = 0; 
    int p = 0; 

    while (p < sizeOf){ 
     if (leftArr[k] < rightArr[m]){ // Left Arr's current value is less 
      newArray[p] = leftArr[k];    // right arr's current calue 
      k++; 
     } 
     else if (leftArr[k] >= rightArr[m]){ 
      newArray[p] = rightArr[k]; 
      m++; 
     } 
     p++; 
    } 

    //for (int i = 0; i < 8; i++) 
    // cout << newArray[i] << endl; 

    return newArray;    // Return address to new array 

} 

Answer 1

Существует фундаментальная проблема дизайна в вашем MergeSort():

• ваш алгоритм является рекурсивным (который идеально подходит)
• , к сожалению, она возвращает newArray который static. Это означает, что все вызовы используют один и тот же экземпляр одной и той же статической переменной (и перезаписывают тот, который возвращается рекурсивным вызовом).

Вам нужно решить это, сделав newArray нестационарным. И в конце функции вам необходимо вернуть delete[] массивы, возвращаемые рекурсивными вызовами, чтобы избежать утечки памяти.