Merge Sort - help me debug

Hello forum visitors! :-)

Recently I have started learning algorithms (starting with sort-ones). I am having a little trouble with merge sort. I understand how it theoretically works, but I seem to be unable to make a correct implementation. I have found multiple code examples and, looking up to them, I have tried over 10 times, but to no avail. The code compiles, but it doesn't do what it should. I am hoping you will be able to determine the logical mistake I have made, or at least give me a hint how to track it down. Thank you in advance.

main:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include "mSortGM.h"
#include <time.h>
#include <iostream>
using namespace std;

int main()
{
   short num = 21;
   short* a = new short[num];  
   srand(time(0));
   
   for (short i=0; i<num; ++i)
	  a[i] = rand()%200 - 100;
   
   mergeSort(a, num);
   
   for(short i=0; i<num; ++i)
	  cout<<a[i]<<" ";
   
    return 0;
}


Sorting (file: mSortGM.h):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
void mergeSplit (short* array, short startP, short endP);
void merge (short* arr,short sP, short mP, short eP);

void mergeSort (short* arr, short size)
{
   mergeSplit (arr,0,(size-1));
}

void mergeSplit (short* array, short startP, short endP)
{
   
   if (startP < endP)
   {
	  short midP = (startP + endP) / 2;
	  mergeSplit (array, startP, midP);
	  mergeSplit (array, (midP+1), endP);
	  merge(array, startP, midP, endP);
   }
}

void merge (short* arr,short sP, short mP, short eP)
{
   short leftIter = sP;
   short rightIter = mP+1;
   short tempIter = 0;
   
   short tempSize = (eP -sP)+1;
   short* tempArr = new short[tempSize];
   
   while ((leftIter <= mP) && (rightIter <= eP))
   {
	  if (arr[leftIter] <= arr[rightIter])
	  {
		 tempArr[tempIter] = arr[leftIter];
		 ++tempIter;
		 ++leftIter;
	  }
	  
	  else
	  {
		 tempArr[tempIter] = arr[rightIter];
		 ++tempIter;
		 ++rightIter;
	  }
	  
	  if (leftIter > mP)
	  {
		 for (; rightIter <= eP; ++rightIter, ++tempIter)
			tempArr[tempIter] = arr[rightIter];
	  }
	  
	  else
	  {
		 for (; leftIter <= mP; ++leftIter, ++tempIter)
			tempArr[tempIter] = arr[leftIter];
	  }
   }
   
   for (short i=0, j=sP; j<=eP; ++i, ++j) arr[j] = tempArr[i];
   
   delete[] tempArr;
}

Topic archived. No new replies allowed.