I'm going through the book Introduction to Algorithms.  I made a comparison between merge-sort for an array of integers versus a vector.Could I have structured this program better?  Why is the vector version so much slower?  Sorting 2 million integers with a vector type took almost 2 seconds but sorting the same list using an array only took .4 seconds.  Also, if I increase arraylength to over 3 million, then I get a segmentation fault.  How can I avoid this?I am used to Mathematica and Python, but not C++.  In what way have I made use of pointers here?  How could I better make use of them?#include <iostream>#include <math.h>#include <vector>#include <chrono>using namespace std;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 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    int L[n1+1];    int R[n2+1];    for(int i=0;i<=n1-1; i++)    {        L[i]=A[p+i];    }    for(int j=0;j<=n2-1; j++)    {        R[j]=A[q+1+j];    }    //Create a sentinal value for L and R that is larger than the largest    //element of A    int largest;    if(L[n1-1]<R[n2-1]) largest=R[n2-1]; else largest=L[n1-1];    L[n1]=largest+1;    R[n2]=largest+1;    //Merge the L and R lists    int i=0;    int j=0;    for(int k=p; k<=r; k++)    {        if (L[i]<=R[j])        {            A[k]=L[i];            i++;        } else        {            A[k]=R[j];            j++;        }    }}void merge_sort(int A[], int p, int r){    if(p<r)    {        int q=floor((p+r)/2);        merge_sort(A,p,q);        merge_sort(A,q+1,r);        merge(A,p,q,r);    }}void vmerge(vector<int>& A, 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    vector<int> L(&A[p],&A[q+1]);    vector<int> R(&A[q+1],&A[r+1]);    //Create a sentinal value for L and R that is larger than the largest    //element of A    int largest;    if(L[n1-1]<R[n2-1]) largest=R[n2-1]; else largest=L[n1-1];    L.push_back(largest+1);    R.push_back(largest+1);    //Merge the L and R lists    int i=0;    int j=0;    for(int k=p; k<=r; k++)    {        if (L[i]<=R[j])        {            A[k]=L[i];            i++;        } else        {            A[k]=R[j];            j++;        }    }}void vmerge_sort(vector<int>& A, 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,p,q);        vmerge_sort(A,q+1,r);        vmerge(A,p,q,r);    }}    int main(){    //seed the random number generator    srand(time(0));    cout<<C++ merge-sort test<<endl;    //vlist is defined to be of type vector<int>    vector<int> vlist1;    //rlist1 is defined to be an integer array    int *rlist1= new int[arraylength];    //both vlist1 and rlist1 have the same content, 2 million random integers    for(int i=0;i<=arraylength-1;i++)    {        rlist1[i] = rand() % 10000;        vlist1.push_back(rlist1[i] );    }    //here I sort rlist1    auto   t1 = std::chrono::high_resolution_clock::now();    merge_sort(rlist1,0,arraylength-1);    auto   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,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;}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.
Implementation of the merge_sort - comparing the timing of an array versus a vector
c++;mergesort