UPDATE: Here is the code I've gotten to after reading Loki Astari and Aleksey Demakov's answers. With the code above, I was able to sort 2 million random numbers in 400 ms using merge_sort and 1926 ms using vmerge_sort. After making the changes, these functions do the task in 410 ms and 860 ms, respectively. So working with the vector type takes twice as long. I suppose this shouldn't be a suprise, as it states here "Therefore, compared to arrays, vectors consume more memory in exchange for the ability to manage storage and grow dynamically in an efficient way."
#include <iostream>
#include <math.h>
#include <vector>
#include <chrono>
//Is this less offensive than using the entire std namespace?
using std::cout;
using std::endl;
const int arraylength=2000000;
//This is an implementation of merge_sort, an algorithm to sort a list of integers using
//a recursion relation. The merge_sort is written as two functions, `merge` which takes two
//pre-sorted lists and merges them to a single sorted list. This is called on by merge_sort,
//which also recursively calls itself.
//I've implemented it here twice, first with the two functions `merge` and `merge_sort`, and then
//again with `vmerge` and `vmerge_sort`. The first two take as their argument arrays of integers,
//while the second two take the data type `vector` from the `vector` package (is package the right word?
//or do I say library?).
void merge(int A[], int LA[], int RA[], int p, int q, int r)
{
//n1 and n2 are the lengths of the pre-sorted sublists, A[p..q] and A[q+1..r]
int n1=q-p+1;
int n2=r-q;
//Copy the left and right halves of the A array into the L and R arrays
for(int i=0;i<n1; i++)
{
LA[i]=A[p+i];
}
for(int j=0;j<n2; j++)
{
RA[j]=A[q+1+j];
}
//Merge the L and R lists
int i=0;
int j=0;
int k = p;
while(i < n1 && j < n2) {
A[k++] = (LA[i]<=RA[j])
? LA[i++]
: RA[j++];
}
while(i < n1) {
A[k++] = LA[i++];
}
while(j < n2) {
A[k++] = RA[j++];
}
}
void merge_sort(int A[], int LA[], int RA[], int p, int r)
{
//This recursively splits the array A into smaller sections
if(p<r)
{
int q=floor((p+r)/2);
merge_sort(A,LA,RA,p,q);
merge_sort(A,LA,RA,q+1,r);
merge(A,LA,RA,p,q,r);
}
}
void vmerge(std::vector<int>& A, std::vector<int>& LA, std::vector<int>& RA, int p, int q, int r)
{
//n1 and n2 are the lengths of the pre-sorted sublists, A[p..q] and A[q+1..r]
int n1=q-p+1;
int n2=r-q;
//copy these pre-sorted lists to L and R
for(int i=0;i<n1; i++)
{
LA[i]=A[p+i];
}
for(int j=0;j<n2; j++)
{
RA[j]=A[q+1+j];
}
//Merge the L and R lists
int i=0;
int j=0;
int k = p;
while(i < n1 && j < n2)
{
A[k++] = (LA[i]<=RA[j])
? LA[i++]
: RA[j++];
}
while(i < n1) {
A[k++] = LA[i++];
}
while(j < n2) {
A[k++] = RA[j++];
}
}
void vmerge_sort(std::vector<int>& A, std::vector<int>& LA, std::vector<int>& RA, int p, int r)
{
//This recursively splits the vector A into smaller sections
if(p<r)
{
int q=floor((p+r)/2);
vmerge_sort(A,LA,RA,p,q);
vmerge_sort(A,LA,RA,q+1,r);
vmerge(A,LA,RA,p,q,r);
}
}
int main()
{
//seed the random number generator
srand(time(0));
std::chrono::high_resolution_clock::time_point t1,t2;
cout<<"C++ merge-sort test"<<endl;
//rlist1 is defined to be an integer array
//L and R are the subarrays used in the merge function
int *rlist1= new int[arraylength];
int halfarraylength=ceil(arraylength/2)+1;
int *R= new int[halfarraylength];
int *L= new int[halfarraylength];
//vlist is defined to be of type vector<int>
//vL and vR are the left and right subvectors used in the vmerge function
std::vector<int> vlist1,vL,vR;
vlist1.reserve(arraylength);
vL.reserve(halfarraylength);
vR.reserve(halfarraylength);
//both vlist1 and rlist1 have the same content, 2 million random integers
for(int i=0;i<=arraylength-1;i++)
{
rlist1[i] = rand() % 1000000;
vlist1[i] = rlist1[i];
}
//here I sort rlist1
t1 = std::chrono::high_resolution_clock::now();
merge_sort(rlist1,L,R,0,arraylength-1);
t2 = std::chrono::high_resolution_clock::now();
cout << "sorting "<<arraylength<<" random numbers with merge sort took "
<< std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count()
<< " milliseconds\n";
//here I sort vlist1
t1 = std::chrono::high_resolution_clock::now();
vmerge_sort(vlist1,vL,vR,0,arraylength-1);
t2 = std::chrono::high_resolution_clock::now();
cout << "sorting "<<arraylength<<" random numbers with vmerge sort took "
<< std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count()
<< " milliseconds\n";
//Now we test that both sorted lists are identical
cout << "Testing that both sorted lists are the same"<< endl;
int testcounter = 0;
for (int k=0; k< arraylength; k++)
{
if (rlist1[k] != vlist1[k]) testcounter+=1;
}
if (testcounter==0) cout<< "Both lists are the same\n"; else cout<<"Both lists are not the same\n";
}
Both answers have been very helpful. How does accepting an answer on this stackexchange work, since you aren't specifically asking a question, but asking for comments on how to improve something.
