Merge Sort Errors

[waranthem]

Program is running. But it is only displaying 0 values rather than the sorted values. It is also displaying an 'abort trap 6 error'. What could be going wrong?

[Ganado]

Instead of starting with 100, let's start with 1, or 2, or 10. Let's do 2.

Recursion is always confusion, but I think your code is hard to follow, because you have a bunch of variables like "i" "iA" "iB" "j" and "k" and you're doing a disorderly incrementing of them inside mergeArray. You have to keep track of like 10 things at once...

Contents of Array

Number #1 68
Number #2 98

Contents of Array

Number #1 0
Number #2 0

So our array is {68, 98}.

std::cout << "mergeSort(arr, " << beginIndex << ", " << endIndex << ")\n";
If you add print statements* at the beginning of your functions, you'll see that the the functions called looks like this:

mergeSort(arr, 0, 2)
mergeSort(arr, 0, 1)
mergeSort(arr, 0, 0)
mergeSort(arr, 1, 1)
mergeArray(arr, 0, 0, 1)
mergeSort(arr, 2, 2)
mergeArray(arr, 0, 1, 2)

*really, you should be using a debugger and stepping through the code LINE BY LINE and stopping when you see something that isn't right.

Let's look at the mergeArray(arr, 0, 0, 1) call:

int i = 0;
int j = 0;
int k = 0;
int iA = 0 - 0;
int iB = 1 - 0;
int *tempArr1 = new int [0];
int *tempArr2 = new int [1];

OK so far, but creating a [0]-length dynamic array is weird...

First for loop: doesn't run.
Second for loop:
  tempArr2[0] = arr [0] = 68;
  j = 1; 

Still OK...

First while loop: Doesn't run (j==1 is not less than 1)

Second while loop: (0 <= 0)
  !!! Here, we are trying to access arr [k ++] = tempArr1 [i ++];
  tempArr1 has a size of 0, it has no elements!
  This is undefined behavior, your program is now wrong

Third while loop:
            arr [k ++] = tempArr2 [j ++];
  Undefined behavior (again), you are trying access tempArr2[1], which doesn't exist

Let's look at the mergeArray(arr, 0, 1, 2) call:

int i = 0;
int j = 0;
int k = 0;

int iA = 1 - 0 = 1;
int iB = 2 - 1 = 1;

int *tempArr1 = new int [1];
int *tempArr2 = new int [1];

First for loop:
tempArr1[0] = arr [0 + 0] = 68;
i = 1

Second for loop:
tempArr2[0] = arr[0 + 0 + 1] = 98;
j = 1

First while loop:
while (1 < 0 ...) --> Doesn't run

Second while loop:
while (1 <= 1) --> OK

arr [0] = tempArr1 [1]; // UNDEFINED BEHAVIOR, tempArr1 doesn't have a 2nd index!
k = 1;
i = 2;

...

______________________________________

You are accessing out-of-bound indices. Been a while since I've tried to make a recursive merge sort, but it looks like you have some fencepost "off-by-1" errors. I suggest going through your logic carefully and figuring out what to fix, starting with a test array of size 1, then a test array of size 2, then a test array of size 3.

Sort the test arrays by hand, and then try to fix your code's logic

Also, every time you call mergeArray, you're allocating two new temporary arrays that you never delete. You're creating a memory leak here. But that isn't what's causing the errors.