MTH 4300: Algorithms, Computers, and Programming II

Merge Sort

Merge sort has complexity \(O(n\log n)\), where \(n\) is the length of the sequence. The algorithm consists of the following four steps:

Merging two sorted sequences can be done with one passage through the sequence.

#include<iostream>
void mTwoSortedSeq(long* sA, long* sB, long* sM, long k, long l){
    long wA=0, wB=0, wM=0;
    while( (wA < k) || (wB < l) ){
        if(wA==k){
            sM[wM]=sB[wB]; ++wB; ++wM;
        }
        else{
            if(wB==l){
                sM[wM]=sA[wA]; ++wA; ++wM;
            }
            else{
                if(sA[wA] < sB[wB]){
                    sM[wM]=sA[wA]; ++wA; ++wM;
                }
                else{
                    sM[wM]=sB[wB]; ++wB; ++wM;
                }
            }
        }
    }
}


void mergeSort(long* seq, long n){
    if(n > 1){
        //Step 1:
        long m=n/2;
        //Step 2:
        mergeSort(seq,m);
        //Step 3:
        mergeSort(seq+m,n-m);
        //Step 4:
        long* sM=new long[n];
        //The same as: long* sM; sM=new long[n];
        mTwoSortedSeq(seq,seq+m,sM,m,n-m);
        // m is the length of the "left" sorted seq,
        // whose pointer to the first term is seq;
        // n-m is the length of the "right" sorted sequence,
        // whose pointer to the first term is (seq+m)
        
        // Final steps: Copy the sequence sM into seq
        for(long i=0;i < n;++i){seq[i]=sM[i];}
        // Prevent memory leak:
        delete[] sM;
    }
}
int main(){
    long n;
    std::cin>>n;
    long* x;
    x=new long[n];
    for(long i=0;i < n;++i){
        std::cin>>x[i];
    }
    mergeSort(x,n);
    std::cout<<"Sorted sequence is \n";
    for(long i=0;i < n;++i){
        std::cout<< x[i] << " ";
    }
    std::cout<< "\n";
    
    delete[] x;
    return 0;
}