title: quicksort and mergesort bad memory alloc (not sorting over 32k elements)
body: <p>FIXED - I included .cpp files too, cause of linker problems with template class - I had a memory leak in mergesort.cpp, which caused quicksort (included after) to not work too. Introsort was included before, so worked fine. </p>
  
  <p>my qsort algorithm:</p>
  
  <pre><code>#include "quicksort.h"
  
  template &lt;class typ&gt; 
  void quicksort(typ* tab, long int begin, long int end) {
    long int i = begin; 
    long int j = end;
    typ tmp;
    typ pivot = tab[(begin + end) / 2];
  
    /* podziel */
    while (i &lt;= j) {
          while (tab[i] &lt; pivot)
                i++;
          while (tab[j] &gt; pivot)
                j--;
          if (i &lt;= j) {
                tmp = tab[i];
                tab[i] = tab[j];
                tab[j] = tmp;
                i++;
                j--;
          }
    };
  
    /* rekurencja */
    if (begin &lt; j)
          quicksort(tab, begin, j);
    if (i &lt; end)
          quicksort(tab, i, end); 
  }
  </code></pre>
  
  <p>I've build this in 2 different computers with Visual Studio 11 (win 64) and with dev c++. Same happens to my mergesort. 32002 elements and no more. </p>
  
  <p>mergesort:</p>
  
  <pre><code>#include "mergesort.h"
  
  using namespace std;
  
  
  template &lt;class typ&gt;
  void merge(typ *tab, long int begin, long int mid, long int end){
   typ *tab_pom = new typ[end+1];
   long int  i,j,k;
  
   i=begin; //pierwsza czesc
   j=mid+1; //druga czesc
   k=0;
  
   while ( (i&lt;=mid) &amp;&amp; (j&lt;=end) ){ //pierwsze mniej niz srodek drugie mniej niz koniec
             if(tab[i] &lt; tab[j]){
                  tab_pom[k]=tab[i];
                  i++;
                  k++;
             }else{
                  tab_pom[k]=tab[j];                
                  j++;
                  k++;
             }   
   }
  
   if (!(i&lt;=mid)){
        while(j&lt;=end){  
             tab_pom[k]=tab[j];
             k++;
             j++;
        } 
   }else{
  
        if (!(j&lt;=end)){
             while(i&lt;=mid){
                  tab_pom[k]=tab[i];
                  k++;
                  i++;
             } 
        }
   }
   k=0;
   for (i=begin;i&lt;=end;i++){
        tab[i]=tab_pom[k];
        k++;
   }         
  }
  
  
  // dzieli dane az do otzrymania posortowanych tablic jedno elementowych
  
  template &lt;class typ&gt;
  void merge_sort(typ *tab, long int begin, long int end){
   long int mid;
  
   if (begin &lt; end){
        mid=(begin+end)/2;
        merge_sort(tab,begin,mid);
        merge_sort(tab,mid+1,end);
        merge(tab,begin,mid,end);
   }    
  }
  </code></pre>
  
  <p>I've wrote also introsort, which works perfect for any amount of elements. I tried increasing stack size in Visual Studio 11 -> project -> properties -> linker -> stack reserve size -> 80000000. Nothing changes. Any help appreciated.</p>
  
  <p>source:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;time.h&gt;
  #include "introspectiv.h"
  #include "introspectiv.cpp"
  #include "mergesort.h"
  #include "mergesort.cpp"
  #include "quicksort.h"
  #include "quicksort.cpp"
  
  using namespace std;
  
  //funkcja do kopiowania tablicy 
  template&lt;class typ&gt;
  void kopiuj(typ* tabl_1, typ* tabl_2, int indeks){
  for (int i = 0 ; i &lt; indeks ; i++) tabl_2[i] = tabl_1[i];
  }
  
  int main() {
  //tworzy tablice
  cout &lt;&lt; "podaj rozmiary tablicy wypelnionej losowymi liczbami: ";
  int wybor;
  clock_t czas[7];
  clock_t start, stop;
  long int n, i, end, begin;
  cin &gt;&gt; n;
  int *tablica = new int[n];
  int *tab_pom = new int[n];
  for (i=0; i&lt;n; i++){
      tablica[i] = rand() % 100;
  }
  
  end = n-1;
  begin = 0;
  
  float procent[] = {0, 0.25, 0.5, 0.75, 0.95, 0.99, 0.997};
  
  cout &lt;&lt; endl &lt;&lt; "wybierz algorytm sortowania: " &lt;&lt; endl;
  cout &lt;&lt; "quicksort - 1 " &lt;&lt; endl;
  cout &lt;&lt; "mergesort - 2 " &lt;&lt; endl;
  cout &lt;&lt; "introspektywne - 3 " &lt;&lt; endl;
  cin &gt;&gt; wybor;
  switch (wybor)
  {
  case 1: {
      for (i=0; i&lt;7; i++){
          kopiuj(tablica, tab_pom, end);
          end = end*procent[i]; 
          quicksort(tab_pom, begin , end);
  
          end = n-1;
          start=clock();
          quicksort(tab_pom, begin , end);
          stop=clock();  
          czas[i] = stop-start;
  
              }
          }
  
  case 2: {
      start=clock();  
      merge_sort(tablica, begin , end);
      stop=clock();
          }
  case 3: {
      start=clock();
      introspective(tablica, n);
      stop=clock();
          }
  default: break;
      }
  
  
  //for (i=0; i&lt;n; i++){
  //  cout&lt;&lt;tablica[i]&lt;&lt; " ";
  //}
  
  cout &lt;&lt; endl &lt;&lt; "Czas wybranego sortowania: " &lt;&lt; endl; 
  
  for (i=0; i&lt;7; i++){
  cout &lt;&lt; "Dla " &lt;&lt; procent[i]*100 &lt;&lt; "% posortowanych danych: " &lt;&lt; czas[i] &lt;&lt; " ms"    &lt;&lt; endl &lt;&lt; endl;
  }
  system("pause");
  }
  </code></pre>
  
  <p>its not finished for counting times in intro and mergesort. </p>