Merge/Insertion sort program taking longer than an hour to finish - C++ My program uses merge and insertion sort to sort a set of numbers.
It works perfectly fine for small inputs, less than 2 seconds for 1,000 ints. But I need to sort 1,000,000 ints. When I try with 1 million, it takes over 2 hours to sort. Can someone please help me optimize this program so it works faster?
FYI: I have several versions of this program because I have been trying to make it faster. Originally, my program would read 1 million ints from a text file, sort, then output the sorted numbers to a text file. But I assumed that was taking a large portion of the running time so I took that out completely.
Instead, I initialized the vector with 1,000,000 ints in the main program, like so:
vector&lt;int&gt; vec {7000, 8090, 189, 19, 0, 29032, ... ,90};

Again, my program works great with small input sizes. Any advice? Thank you!
#include&lt;iostream&gt;
#include&lt;vector&gt;
#include &lt;time.h&gt;
#include &lt;stdio.h&gt;
#include&lt;fstream&gt;

using namespace std;

void merge(vector&lt;int&gt; &amp;vec, int left, int center, int right, int originalsize)
{
   int leftVsize, rightVsize; //left and right vector sizes
   vector&lt;int&gt; vec1;

   leftVsize = center-left+1;            //calculating left and right temporary vector sizes
   rightVsize = right - center;

   vector&lt;int&gt; tempLeft(leftVsize);     //initializing temp left and right vectors
   vector&lt;int&gt; tempRight(rightVsize);

   for(int i = 0; i &lt; tempLeft.size(); ++i)
   {
     tempLeft.at(i) = vec.at(left+i);      //initializing left vector
   }

   for(int i = 0; i &lt; tempRight.size(); ++i)
   {
      tempRight.at(i) = vec.at(i+center+1);   //initializing right vector
   }

   int i = left, j = 0, k = 0;

   while((j &lt; tempLeft.size()) &amp;&amp; (k &lt; tempRight.size()))      //while left and right vector have elements
   {
      if(tempLeft.at(j) &lt;= tempRight.at(k))     //if left element is smaller
      {
        vec.at(i) = tempLeft.at(j);   //add value to original vector
        j++;
      }
      else      //else
      {
        vec.at(i) = tempRight.at(k);      //add value to original vector
        k++;
      }
     i++;
   }

 while(j &lt; tempLeft.size())      //while left vector has elements
 {
    vec.at(i++) = tempLeft.at(j++);
 }

 while(k &lt; tempRight.size())     //while right vector has elements
 {
    vec.at(i++) = tempRight.at(k++);
 }

}

void insertionSort(vector&lt;int&gt; &amp;vec, int originalsize)
{
   for(int i = 1; i &lt; originalsize; ++i)     //starting from 1 for original vector size
  {
    int tempval = vec[i];      //set tempval to vector value at 1
    int j = i;                    //j now equals i

    for(j = i; ((j &gt; 0)&amp;&amp;(tempval &lt; vec[j-1])); --j)    //for j=i while j is greater than 0 and tempval is less than the number before it
    {
      vec[j] = vec[j-1];    //set vector[j] to vector[j-1]
 }
      vec[j] = tempval;   //tempval now holds vec[j]
}
}

void sort(vector&lt;int&gt; &amp;vec, int left, int right, int originalsize)
{
  int insertion = right - left;
  if(insertion &lt;= 8)    //if righ-left is less than or equal to 8
  {
     insertionSort(vec, originalsize);       // call insertion sort
  }
  if(left &lt; right)
  {
    int center = (left+right)/2;    //calculating center of vector
    sort(vec, left, center, originalsize);    //calling sort for temp vector
    sort(vec, center+1, right, originalsize);   //calling sort for temp vector
    merge(vec, left, center, right, originalsize);    //calling merge to merge two vectors together
  }
 }

int main()
{
  vector&lt;int&gt; vec { 1 million ints };
  int temp;
  clock_t q, q1, q2,t;


  int orgsize = vec.size();

  q=clock();

  sort(vec, 0, (vec.size()-1), orgsize);    //calling sort function

  q=clock()-q;

  cout &lt;&lt; &quot;Total Time: &quot;&lt;&lt; ((float)q)/CLOCKS_PER_SEC &lt;&lt;&quot;\n&quot;;
 return 0;
}
Performance
For the moment, let's look at only one small part:
void sort(vector&lt;int&gt; &amp;vec, int left, int right, int originalsize)
{
  int insertion = right - left;
  if(insertion &lt;= 8)    //if righ-left is less than or equal to 8
  {
     insertionSort(vec, originalsize);       // call insertion sort
  }
  if(left &lt; right)
  {
    int center = (left+right)/2;    //calculating center of vector
    sort(vec, left, center, originalsize);    //calling sort for temp vector
    sort(vec, center+1, right, originalsize);   //calling sort for temp vector
    merge(vec, left, center, right, originalsize);    //calling merge to merge two vectors together
  }
 }

This has a couple of problems. The first has already been pointed out: when you call insertionSort, you're telling it to sort the entire array, rather than just the small section you're currently dealing with.
From there, however, it just gets worse. Because after you do an insertion sort on the entire array, you don't just return can call it good. You continue to call sort recursively as long as left &lt; right.
So that means when you get a partition down to 8 elements, you do insertion sort on the entire array. Then you create two partitions of 4 elements--and for each of them, you insertion sort the whole array again. Then from each of those you create two partitions of 2 elements--and for each of them...yup, you insertion sort the whole array yet again.
So not only are you do an \$O(N^2)\$ insertion sort on the whole array--with the array of a million elements, you're doing it 500,000 + 250,000 + 125,000 = 875,000 times!
Comments
Some of your comments are quite good:
 while(j &lt; tempLeft.size())      //while left vector has elements
 {
     vec[i++] = tempLeft[j++];
 }

That's a real help in showing what your intent was. Some of the other comments aren't nearly so helpful though. For example, none of these strikes me as being very helpful at all:
   for(int i = left; i &lt; right; ++i)     //starting from 1 for original vector size
  {
    int tempval = vec[i];      //set tempval to vector value at 1
    int j;

    for(j = i; ((j &gt; 0)&amp;&amp;(tempval &lt; vec[j-1])); --j)    //for j=i while j is greater than 0 and tempval is less than the number before it
    {
      vec[j] = vec[j-1];    //set vector[j] to vector[j-1]
     }
      vec[j] = tempval;   //tempval now holds vec[j]
}

The last of those goes beyond useless and into misleading (sounds like you think it assigned from vec[j] to tempval, when you actually did the reverse).
Indentation
Indentation is an important tool in keeping code understandable. The precise parameters you choose don't seem to matter a whole lot (within reason), but whatever you do, do it consistently. This code is sadly lacking in that respect.