Thread: Merge sort not sorting at all despite copying it exact from book.

It seems one of my mergesorts isn't sorting at all, not to mention two of my three quicksorts.

        #ifndef _SORTS_H_
        #define _SORTS_H_
        #include <stdlib.h>
        #include <time.h>
        #include <vector>
        using namespace std;
 
 
        class Sorts
        {
         public:
 
          template <class T>
          static void merge_sort(T *array, int size );
 
          private:
 
              template<class T>
              static void merge_sort(T *array, T *tmpArray, int left, int right)
              {
                     if (left < right)
                     {
                            int center = (left+right)/2;
                            merge_sort(array, tmpArray, left, center);
                            merge_sort(array, tmpArray, center+1, right);
                            merge(array, tmpArray, left, center+1, right);  
                              }
                     }
 
                     template<class T>
                     static void merge(T *array, T *tmpArray, int leftPos, int rightPos, int rightEnd)
                     {
                            int leftEnd = rightPos -1;
                            int tmpPos = leftPos;
                            int numElements = rightEnd - leftPos + 1;
 
                            while(leftPos <= leftEnd && rightPos <= rightEnd)
 
                            if(array[leftPos] <= array[rightPos])
                            tmpArray[tmpPos++] = array[leftPos++];
                            else 
                            tmpArray[tmpPos++] = array[rightPos++];
 
                            while(leftPos <= leftEnd)
                            tmpArray[tmpPos++] = array[leftPos++];
 
                            while(rightPos <= rightEnd)
                            tmpArray[tmpPos++] = array[rightPos++];
 
                            for (int i =0; i < numElements; i++, rightEnd--)
                            array[rightEnd] = tmpArray[rightEnd];
 
                            }
 
 
    };
 
    template <class T>
      void Sorts::merge_sort(T *array, int size)
      {
             T *tmpArray = new T[size];
             merge_sort(array, tmpArray, 0, size -1);
             }
 
    #endif

I know the following code won't actually run without the arguments but you can simply delete that part and replace it with a cin and import that instead.

#include "Sorts.h"
#include <iostream>
#include <fstream>
using namespace std;
#include <time.h>
 
int main(int argc,char *argv[])
{
  if (argc!=2)
  { 
    cout <<"Please enter file name."<<endl;
    return -1;
  }
  double *array;
  int length;
 
 
  fstream fin;
 
  fin.open(argv[1]);
  if (!fin.is_open())
  {
    cout <<"Could not open file"<<endl;
    return -1;
  }
 
  fin >>length;
  array = new double[length];
  for (int i=0;i<length;i++)
    fin >> array[i];
 
 
double *clone1;
 
 
clone1 = new double[length];
 
 
 
for (int i =0; i < length; i++)
{
clone1[i] = array[i];
 
}
 
 
 
  delete []array;
 
 
 double time_taken2=0;
Sorts s2;
  clock_t tinitial2 = clock(); //the initial time
 
 // Sorts::insertion_sort(array,length);
    Sorts::merge_sort(array, length);
   // Sorts::quicksort_simple(array, 0, length - 1);
 // Sorts::quicksort_median3(array, length);
// Sorts::quicksort_naive(array, 0, length -1);
 
  clock_t tfinal2 = clock(); //the final time
  time_taken2 = tfinal2-tinitial2; //the difference, this is still in "clock ticks"
  /*
    The resolution of the above clock is about 15 msec., which means that it cannot measure times smaller than 15 msec.
    If the thing you want to measure finishes before that time, the only resort is to do the operation several times, take the total time and take the average
  */
 
 
 
  if (time_taken2==0)  //operation was too fast for this clock, take average
  {
 
    time_taken2 = 0;
    double * tmparray = new double[length];	
    for (int i=0;i<10;i++)
    {	
      //to take true average we run the same algorithm on the same input every time
      /*
	if you sort the original array, all subsequent sorts will be on an 
	already sorted array, which will spoil the average. This is because 
	we know that insertion sort times vary hugely from worst to best case
      */
      for (int j=0;j<length;j++)
	tmparray[j] = clone1[j]; //create same temporary array again
      tinitial2 = clock(); //take initial time here so that temporary array time is not counted
      Sorts::merge_sort(tmparray,length);
      tfinal2 = clock(); //take final time
      time_taken2 += (tfinal2-tinitial2);
    }
    time_taken2 /=10; //average
    delete []tmparray;
  }
  time_taken2 = 1000.0*time_taken2/CLOCKS_PER_SEC; //conversion to milliseconds
  cout << "Time taken(merge sort): "<<time_taken2<< "msec."<<endl;
 
for (int i = 0; i < 500; i++)
{
cout <<clone1[i];
}
 
delete[] clone1;
 
}

I'm wondering if it's the fact that the book used a vector and I'm using an array.

Is it my size value that is messing it up?

The array "array" was there because normally I'm using that array on a function and then copying that array, before it's sorted, four times and using the other four functions with those.

I was able to solve the problem.

Please put thread to sleep. Ha ha!

System.out.println("Thread can be closed now.");
Thread.sleep(Infinity);