Merge/Insertion sort program taking longer than an hour to finish - C++

Question

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<int> vec {7000, 8090, 189, 19, 0, 29032, ... ,90};

Again, my program works great with small input sizes. Any advice? Thank you!

#include<iostream>
#include<vector>
#include <time.h>
#include <stdio.h>
#include<fstream>

using namespace std;

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

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

   vector<int> tempLeft(leftVsize);     //initializing temp left and right vectors
   vector<int> tempRight(rightVsize);

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

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

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

   while((j < tempLeft.size()) && (k < tempRight.size()))      //while left and right vector have elements
   {
      if(tempLeft.at(j) <= 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 < tempLeft.size())      //while left vector has elements
 {
    vec.at(i++) = tempLeft.at(j++);
 }

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

}

void insertionSort(vector<int> &vec, int originalsize)
{
   for(int i = 1; i < 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 > 0)&&(tempval < 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<int> &vec, int left, int right, int originalsize)
{
  int insertion = right - left;
  if(insertion <= 8)    //if righ-left is less than or equal to 8
  {
     insertionSort(vec, originalsize);       // call insertion sort
  }
  if(left < 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<int> 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 << "Total Time: "<< ((float)q)/CLOCKS_PER_SEC <<"\n";
 return 0;
}

Answer 1

Performance

For the moment, let's look at only one small part:

void sort(vector<int> &vec, int left, int right, int originalsize)
{
  int insertion = right - left;
  if(insertion <= 8)    //if righ-left is less than or equal to 8
  {
     insertionSort(vec, originalsize);       // call insertion sort
  }
  if(left < 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 < 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 < 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 < 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 > 0)&&(tempval < 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.

Answer 2

Here's a rewrite incorporating everything said before, as well as an idea I got from Timsort: Instead of moving both halves out for the merge, only move one half out. I chose the left half. This saves space, saves the move costs, and also eliminates the need at the end to move remaining right values, as they're already where they belong. Also, I show the first and last few elements before and after the sort and whether it's actually sorted.

For a million ints it takes about one second on repl.it:

first few: 1804289383 846930886 1681692777
last few: 639902526 2025884438 429357853
total time: 0.988527
first few: 1210 3722 4686
last few: 2147476900 2147477011 2147480021
sorted? true

Here's the code. One note: I used the names first, middle and last, as those are the names C++ itself uses (e.g., in inplace_merge). Also see Why the “begin/end” vs “first/last” discrepancy?.

#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <vector>

template<typename I>
void merge(I first, I middle, I last, I tmp_first) {
  std::move(first, middle, tmp_first);

  I left = tmp_first, left_last = tmp_first + (middle - first);
  I right = middle, right_last = last;
  I write = first;

  while (left != left_last && right != right_last)
    *write++ = *right < *left ? *right++ : *left++;

  std::move(left, left_last, write);
}

template<typename I>
void insertion_sort(I first, I last) {
  if (first == last)
    return;
  for (I i = first + 1; i != last; ++i) {
    int tempval = *i;
    I j = i;
    for (; (j != first) && (tempval < *(j-1)); --j)
      *j = *(j-1);
    *j = tempval;
  }
}

template<typename I>
void sort(I first, I last, I tmp_first) {
  int size = last - first;
  if (size <= 8) {
    insertion_sort(first, last);
  } else {
    I middle = first + size / 2;
    sort(first, middle, tmp_first);
    sort(middle, last, tmp_first);
    merge(first, middle, last, tmp_first);
  }
}

template<typename I>
void sort(I first, I last) {
  std::vector<int> tmp((last - first) / 2);
  sort(first, last, tmp.begin());
}

template<typename I>
void show(std::string label, I first, I last) {
  std::cout << label << ':';
  while (first != last)
    std::cout << ' ' << *first++;
  std::cout << std::endl;
}

template<typename I>
bool is_sorted(I first, I last) {
  if (first == last)
    return true;
  ++first;
  for (; first != last; ++first)
    if (*first < *(first - 1))
      return false;
  return true;
}

int main() {
  // Create vector of n random ints.
  int n = 1000000;
  std::vector<int> data;
  for (int i = 0; i < n; i++)
    data.push_back(rand());

  // Show first and last few elements.
  show("first few", data.begin(), data.begin() + 3);
  show("last few", data.end() - 3, data.end());

  // Sort and show how long it took.
  clock_t q = clock();
  sort(data.begin(), data.end());
  q = clock() - q;
  std::cout << "total time: " << ((float)q) / CLOCKS_PER_SEC << "\n";

  // Show first and last few elements and whether it's indeed sorted.
  show("first few", data.begin(), data.begin() + 3);
  show("last few", data.end() - 3, data.end());
  std::cout << "sorted? " << std::boolalpha
            << is_sorted(data.begin(), data.end()) << std::endl;
}