title: Designing MERGE-SORT Algorithm - VERY WEIRD ISSUE ! "std::bad_alloc at memory location 0x00486F78."
body: <p>This is for an assignment in an algorithm class. I understand and agree that using a vector would simplify things, but that isn't an option.
  The code for the Mergesort / merge algorithm can't be modified either.</p>
  
  <p>I need to run the merge sort as follows:
  starting from 100 all the way to 1000, increments of 100. For each increment I run it 5 times, for each of these times I run it 1000 times.</p>
  
  <p>That being said - everything works fine until my loop reaches 700 and crashes with the error:  "Unhandled exception at 0x75612F71 in msdebug.exe: Microsoft C++ exception: std::bad_alloc at memory location 0x010672F4."</p>
  
  <p>Here is my code:</p>
  
  <pre><code>int const size = 6;
  int const size2 = 1001;
  int const times = 6;
  int const interval = 11;  
  
  void merge(int arr[], int p, int q, int r)
      {
          int n1 = q - p + 1;
          int n2 = r - q;
          int * L = new int[n1 + 1];
          int * R = new int[n2 + 1];    // line giving the error after 700
          for (int i = 1; i &lt;= n1; i++)
          {
              L[i] = arr[p + i - 1];
          }
          for (int j = 1; j &lt;= n2; j++)
          {
              R[j] = arr[q + j];
          }
          L[n1 + 1] = 32768;
          R[n2 + 1] = 32768;
          int i, j;
          i = j = 1;
          for (int k = p; k &lt;= r; k++)
          {
              if (L[i] &lt;= R[j])
              {
                  arr[k] = L[i];
                  i++;
              }
              else
              {
                  arr[k] = R[j];
                  j++;
              }
          }
  
  
      }
  
      void mergeSort(int arr[], int p, int r)
      {
          int q;
          if (p &lt; r)
          {
              q = ((p + r) / 2);
              mergeSort(arr, p, q);
              mergeSort(arr, (q + 1), r);
              merge(arr, p, q, r);
  
  
          }
      }
  
      void copyArray(int original[][size2], int copy[], int row, int finish)
      {
          int i = 1;
          while (i &lt;= finish)
          {
              copy[i] = original[row][i];
              i++;
          }
  
      }
      void copyOneD(int orig[], int cop[])
      {
          for (int i = 1; i &lt; size2; i++)
          {
              cop[i] = orig[i];
          }
      }
  
  
  
      int main()
      {
          struct timeval;
  
          clock_t start, end;
          srand(time(NULL));
  
          int arr[size][size2];
          int arr2[size2];
          int arrCopy[size2];
          double tMergeSort[times][interval];
          double avgTmergeSort[11];
  
  
          /*for (int i = 1; i &lt; (size2); i++)
          {
               arr2[i] = rand();
          }*/
  
          for (int i = 1; i &lt; size; i++)
          {
              for (int j = 1; j &lt; size2; j++)
              {
                  arr[i][j] = rand();
              }
          }
  
  
      for (int x = 100; x &lt;= 1000; x = x + 100)   //This loop crashes &gt;=700
          {
              for (int r = 1; r &lt;= 5; r++)
              {
                  copyArray(arr, arr2, r, 1001);
  
                  for (int k = 0; k &lt; 1000; k++)
                  {
                      copyOneD(arr2, arrCopy);
                      mergeSort(arrCopy, 1, x);
                  }
              }
          }
  
  
          return 0;
      }
  </code></pre>
  
  <p>You can ignore the code and the arrays. Those functions work fine. 
  Everything works fine until I set 'x &lt;= 700' or higher and then it crashes.</p>
  
  <p>I had a theory that maybe the computer runs out of memory for the pointers in the merge algorithm but when I tried to use delete it also crashed.</p>
  
  <p>Any help is appreciated and suggestions as well.</p>
  
  <p>Thanks</p>