マージソートを行うプログラムを作りましたが、手を加えたはずの配列が何も変わらず帰ってきてしまいます。いろいろ調べた結果、mergeで並びを変えたはずの配列がrecMergeSortに戻ってくると変更前に戻ってしまっていました。配列の受けわたしがうまくいっていないのが原因だと思われますが、どこが間違っているのかがわかりません。
main.cpp
#include <iostream>
#include "recFunc.h"
using namespace std;
int main() {
const int NUM_VALUES = 8;
int mergeArray[NUM_VALUES] = {6, 3, 5, 1, 8, 2, 4, 8};
// show starting array
cout << "Starting array is " << endl;
for(int i = 0; i < NUM_VALUES; i++)
cout << mergeArray[i] << " ";
cout << endl;
// now sort it
mergeSort(mergeArray, NUM_VALUES);
// show updated array, should be in ascending order
cout << "Now the array should be sorted" << endl;
cout << " expected: 1 2 3 4 5 6 7 8" << endl;
cout << " actually: ";
for(int i = 0; i < NUM_VALUES; i++)
cout << mergeArray[i] << " ";
cout << endl;
cout << endl << "Done with testing merge sort" << endl << endl;
return 0;
}
recFunc.cpp
#include <iostream>
#include "recFunc.h"
void mergeSort(int* array, int size)
{
recMergeSort(array, size);
}
void recMergeSort(int* array, int size)
{
if(size <= 1)
{
return;
}
int middle = (size - 1) / 2;
int* arrayLeft = new int [middle+1];
int* arrayRight = new int [(size-1)-middle];
for(int i = 0; i < middle+1; i++)
{
arrayLeft[i] = array[i];
}
for(int i = 0; i < (size-1)-middle; i++)
{
arrayRight[i] = array[(middle+1)+i];
}
recMergeSort(arrayLeft, middle+1);
recMergeSort(arrayRight, (size-1)-middle);
int* temp = merge(arrayLeft, middle+1, arrayRight, (size-1)-middle);
array = temp;
}
int* merge(int* arrayLeft, int leftSize, int* arrayRight, int rightSize)
{
int left = 0;
int right = 0;
int leftEnd = leftSize-1;
int rightEnd = rightSize -1;
int* temp = new int [leftSize+rightSize];
while(left <= leftEnd && right <= rightEnd)
{
//if left value is smaller, save the value to temp
if(arrayLeft[left] <= arrayRight[right])
{
temp[left+right] = arrayLeft[left];
left++;
}
//otherwise(right value is smaller), save it
else
{
temp[left+right] = arrayRight[right];
right++;
}
}
while(left <= leftEnd)
{
temp[left+right] = arrayLeft[left];
left++;
}
while(right <= rightEnd)
{
temp[left+right] = arrayRight[right];
right++;
}
return temp;
}
recFunc.h
int* merge(int* arrayLeft, int leftSize, int* arrayRight, int rightSize);
void recMergeSort(int* array, int size);
void mergeSort(int* array, int size);