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.