The code is too long to type out so I linked an easier to re

The code is too long to type out so I linked an easier to read version below:

http://pastebin.com/ryFc4X41

I get this error below when it tries to run the second algorithm:

Unhandled exception at 0x00D344F9 in ALGTAKE2.exe: 0xC00000FD: Stack overflow (parameters: 0x00000001, 0x01002FB8).

My question is how do I fix this? The debugger implies it has something to do with me passing int *&b as an argument in my ALG2 (MERGE-SORT) function, however, it has no issue with it in ALG1 nor ALG 3.

Solution

#include <iostream>
#include <string>
#include<stdlib.h>
#include <time.h>
#include <chrono>
#include <Windows.h>

using namespace std;

void ALG1(int *&, int);
void ALG2(int *&, int, int);
void MERGE(int *&, int, int, int);
void ALG3(int *&, int, int);
int PARTITION(int *&, int, int);

int main()
{
   LARGE_INTEGER frequency;
   LARGE_INTEGER t3, t4;

   QueryPerformanceFrequency(&frequency);
   int delta = 1000;
   int ns = 1000;
   int nf = 20000;
   int m = 10;
   int counter = 0;
   double timealgo1[11];
   double tavgalgo1[21];
   unsigned timediff = 0;
   int *B = new int[nf + 1];
   int ** A = new int *[m + 1];
   for (int i = 1; i <= m; ++i)
   {
       A[i] = new int[nf + 1];
   }

   for (int i = 1; i <= m; i++)
   {
       for (int j = 1; j <= nf; j++)
       {
           A[i][j] = rand();
       }
   }
   cout << \"INSERT SORT\" << endl;
   for (int n = ns; n <= nf; n = n + delta)
   {
       for (int i = 1; i <= m; i++)
       {
           for (int j = 1; j <= n; j++)
           {
               B[j] = A[i][j];
           }
           //auto start_time = std::chrono::high_resolution_clock::now();
           QueryPerformanceCounter(&t3);
           ALG1(B, n);
           QueryPerformanceCounter(&t4);
           //elapsedTime = (t4.QuadPart - t3.QuadPart) * 1000.0 / frequency.QuadPart;
           //auto end_time = std::chrono::high_resolution_clock::now();
           //auto time = end_time - start_time;
           //timealgo1[i][n] = std::chrono::duration_cast<std::chrono::microseconds>(time).count();
           timealgo1[i] = (t4.QuadPart - t3.QuadPart) * 1000.0 / frequency.QuadPart;
       }
       tavgalgo1[n / 1000] = 0;
       for (int a = 1; a <= m; a++)
       {
           tavgalgo1[n / 1000] = tavgalgo1[n / 1000] + (timealgo1[a]);
       }
       tavgalgo1[n / 1000] = tavgalgo1[n / 1000] / m;
   }
   for (int n = ns; n <= nf; n = n + delta)
   {
       cout << tavgalgo1[n / 1000] << \"\\t\";
       if (n == ns)
       {
           cout << \"ns\" << endl;
       }
       else if (n == ns + delta)
       {
           cout << \"ns + delta\" << endl;
       }
       else if (n>ns + delta)
       {
           counter = (n - ns) / delta;
           cout << \"ns +\" << counter << \"delta\" << endl;
       }
   }

   cout << \"MERGESORT\" << endl;
   for (int n = ns; n <= nf; n = n + delta)
   {
       for (int i = 1; i <= m; i++)
       {
           for (int j = 1; j <= n; j++)
           {
               B[j] = A[i][j];
           }
           //auto start_time = std::chrono::high_resolution_clock::now();
           QueryPerformanceCounter(&t3);
           ALG2(B, 1, n);
           QueryPerformanceCounter(&t4);
           //elapsedTime = (t4.QuadPart - t3.QuadPart) * 1000.0 / frequency.QuadPart;

           //auto end_time = std::chrono::high_resolution_clock::now();
           //auto time = end_time - start_time;
           timealgo1[i] = (t4.QuadPart - t3.QuadPart) * 1000.0 / frequency.QuadPart;
       }
       tavgalgo1[n / 1000] = 0;
       for (int a = 1; a <= m; a++)
       {
           tavgalgo1[n / 1000] = tavgalgo1[n / 1000] + (timealgo1[a]);
       }
       tavgalgo1[n / 1000] = tavgalgo1[n / 1000] / m;
   }
   for (int n = ns; n <= nf; n = n + delta)
   {
       cout << tavgalgo1[n / 1000] << \"\\t\";
       if (n == ns)
       {
           cout << \"ns\" << endl;
       }
       else if (n == ns + delta)
       {
           cout << \"ns + delta\" << endl;
       }
       else if (n>ns + delta)
       {
           counter = (n - ns) / delta;
           cout << \"ns +\" << counter << \"delta\" << endl;
       }
   }

   cout << \"QUICKSORT\" << endl;
   for (int n = ns; n <= nf; n = n + delta)
   {
       for (int i = 1; i <= m; i++)
       {
           for (int j = 1; j <= n; j++)
           {
               B[j] = A[i][j];
           }
           //auto start_time = std::chrono::high_resolution_clock::now();
           QueryPerformanceCounter(&t3);
           ALG3(B, 1, n);
           QueryPerformanceCounter(&t4);
           //auto end_time = std::chrono::high_resolution_clock::now();
           //auto time = end_time - start_time;
           timealgo1[i] = (t4.QuadPart - t3.QuadPart) * 1000.0 / frequency.QuadPart;
       }
       tavgalgo1[n / 1000] = 0;
       for (int a = 1; a <= m; a++)
       {
           tavgalgo1[n / 1000] = tavgalgo1[n / 1000] + (timealgo1[a]);
       }
       tavgalgo1[n / 1000] = tavgalgo1[n / 1000] / m;
   }

   for (int n = ns; n <= nf; n = n + delta)
   {
       cout << tavgalgo1[n / 1000] << \"\\t\";
       if (n == ns)
       {
           cout << \"ns\" << endl;
       }
       else if (n == ns + delta)
       {
           cout << \"ns + delta\" << endl;
       }
       else if (n>ns + delta)
       {
           counter = (n - ns) / delta;
           cout << \"ns +\" << counter << \"delta\" << endl;
       }
   }
   return 0;
}

void ALG1(int *& b, int n)
{
   int key = 0;
   int i = 0;
   for (int j = 2; j <= n; j++)
   {
       key = b[j];
       i = j - 1;
       while (i > 0 && b[i] > key)
       {
           b[i + 1] = b[i];
           i = i - 1;
       }
       b[i + 1] = key;
   }

}

void ALG2(int *&b, int p, int r)
{
   if (p < r)
   {
       int q = p + r / 2;
       ALG2(b, p, q);
       ALG2(b, q + 1, r);
       MERGE(b, p, q, r);
   }

}

void MERGE(int *&b, int p, int q, int r)
{
   int leftLength = q - p + 1;
   int rightLength = r - q;
   int *L = new int[leftLength + 1];
   int *R = new int[rightLength + 1];

   for (int i = 1; i <= leftLength; i++)
   {
       L[i - 1] = b[p + i - 1];
   }

   for (int j = 1; j <= rightLength; j++)
   {
       R[j - 1] = b[q + j];
   }

   L[leftLength] = 999;
   R[rightLength] = 999;

}

void ALG3(int *&b, int p, int r)
{
   if (p < r)
   {
       int q = PARTITION(b, p, r);
       ALG3(b, p, q - 1);
       ALG3(b, q + 1, r);
   }
}
int PARTITION(int*&b, int p, int r)
{
   int x = b[r];
   int hold = 0;
   int i = p - 1;
   for (int j = p; j < r; j++)
   {
       if (b[j] <= x)
       {
           i++;
           hold = b[i];
           b[i] = b[j];
           b[j] = hold;
       }
   }
   b[r] = b[i + 1];
   b[i + 1] = x;
   return i + 1;
}