title: Weird bug in C++ involving new and delete[] functions
body: <p>I'm working on the first programming homework on Coursera's <em>Algorithms: Design and Analysis</em> course ( <a href="https://www.coursera.org/course/algo" rel="nofollow">https://www.coursera.org/course/algo</a> ).
  It involves using merge sort to count inversions ( <a href="http://en.wikipedia.org/wiki/Inversion_(discrete_mathematics" rel="nofollow">http://en.wikipedia.org/wiki/Inversion_(discrete_mathematics</a>) ). I thought this would be a relative no-brainer because I've encountered merge sort before (in school).</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;fstream&gt;
  
  using namespace std;
  
  int *half(int *array, int n, int start, int end)
  {
      /*
       * Creates a new array which contains elements from ''array'' starting with ''start''
       * and ending with ''end - 1''.
       */
  
       int *new_array = new int[end-start];
  
       for(int i = start; i &lt; end; i++)
       {
          new_array[i-start] = array[i];
       }
  
       return new_array;
  }
  
  int merge(int *array1, int n1, int *array2, int n2, int *new_array)
  {
      /*
       *  Merges arrays 1 and 2 (with lengths n1 and n2) into a new_array, counting
       *  ''split inversions'' by the way.
       */
      int i = 0, j = 0, count = 0;
  
      for(int k = 0; k &lt; n1 + n2; k++)
      {
  
           if(i &gt;= n1)
          {
              new_array[k] = array2[j];
              j++;
              continue;
          }
  
           if(j &gt;= n2)
          {
  
              new_array[k] = array1[i];
              i++;
              continue;
          }
  
          if( array1[i] &lt;= array2[j] )
          {
              new_array[k] = array1[i];
              i++;
          }
          else
          {
              new_array[k] = array2[j];
              j++;
              count++;
          }
      }
  
      return count;
  }
  
  int mergesort(int *array, int n)
  {
  
      if(n == 1) return 0; //base case
  
      int x, y, z;
      int odd;
  
      if(n%2 == 0) odd = 0;
      else odd = 1;
  
      int *half1 = new int [n/2];
      int *half2 = new int [n/2 + odd];
  
      half1 = half(array, n, 0, n/2);
      half2 = half(array, n, n/2, n);
  
      x = mergesort(half1, n/2);
      y = mergesort(half2, n/2 + odd);  //if n is odd, we add one
      z = merge(half1, n/2, half2, n/2 + odd, array); //we write a sorted array back in our starting array
  
      delete [] half1;
      delete [] half2;
  
      return x + y + z;
  }
  
  int main()
  {
      int n;
      int *array = new int[n];
  
      cin &gt;&gt; n;
  
      for(int i = 0; i &lt; n; i++)
      {
          int x;
          cin &gt;&gt; x;
          array[i] = x;
      }
  
      for(int i = 0; i &lt; n; i++)
          cout &lt;&lt; array[i] &lt;&lt; " ";
  
      cout &lt;&lt; endl;
      cout &lt;&lt; "Number of inversions: " &lt;&lt; mergesort(array, n) &lt;&lt; endl;
  
      for(int i = 0; i &lt; n; i++)
      cout &lt;&lt; array[i] &lt;&lt; " ";
  
      cout &lt;&lt; endl;
      delete[] array;
  
      return 0;
  }
  </code></pre>
  
  <p>So, what is so weird here?
  First thing: For me, it works perfectly for some arrays, but crashes for other arrays (examples later).
  Second thing: I sent code to my friend who said that everything is working fine for him, even the examples that crash dramatically for me.</p>
  
  <p>So, examples:</p>
  
  <p>For array [1 2 3 4 5 6 7] g++ produces this:</p>
  
  <pre><code>malloc.c:2451: sYSMALLOc: Assertion `(old_top == (((mbinptr) (((char *) &amp;((av)-&gt;bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) &amp;&amp; old_size == 0) || ((unsigned long) (old_size) &gt;= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 * (sizeof(size_t))) - 1)) &amp; ~((2 * (sizeof(size_t))) - 1))) &amp;&amp; ((old_top)-&gt;size &amp; 0x1) &amp;&amp; ((unsigned long)old_end &amp; pagemask) == 0)' failed.
  Aborted (core dumped)
  </code></pre>
  
  <p>When I ''backtrack'' it using gdb:</p>
  
  <pre><code>#0  0x00007ffff7753445 in __GI_raise (sig=&lt;optimized out&gt;) at ../nptl/sysdeps/unix/sysv/linux/raise.c:64
  #1  0x00007ffff7756bab in __GI_abort () at abort.c:91
  #2  0x00007ffff779abed in __malloc_assert (assertion=&lt;optimized out&gt;, file=&lt;optimized out&gt;, line=&lt;optimized out&gt;, function=&lt;optimized out&gt;) at malloc.c:300
  #3  0x00007ffff779e0f4 in sYSMALLOc (av=0x7ffff7ad3720, nb=32) at malloc.c:2448
  #4  _int_malloc (av=0x7ffff7ad3720, bytes=12) at malloc.c:3892
  #5  0x00007ffff779fa45 in __GI___libc_malloc (bytes=12) at malloc.c:2924
  #6  0x00007ffff7b8fded in operator new(unsigned long) () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
  #7  0x00007ffff7b8ff09 in operator new[](unsigned long) () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
  #8  0x0000000000400b12 in mergesort (array=0x603010, n=7) at jedan.cpp:81
  #9  0x0000000000400cfe in main () at jedan.cpp:120
  </code></pre>
  
  <p>It does something similar (but not <strong>the same</strong>!) for the array [1 2 3 4 5 6 7 8 9 10], again connected to the new and delete[] functions. I can post it here later if somebody thinks that would be helpful, but I don't want to bloat this post too much.
  And it works for most of the arrays I tried (I had no problems with arrays of size &lt;= 6, and for a pretty big number of bigger arrays).</p>
  
  <p>I'm using Ubuntu 12.04, installed yesterday... pretty clean and fresh.
  Help?</p>
  
  <p>P.S. If you find variable names a little weird, sorry... I translated them from my native language so the code could be more readable.</p>