## 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:

• Step 1. Divide sequence into two parts: Left and Right. The two parts should be of the same size or have their sizes differ by $$1$$.
• Step 2. Sort the left (using merge sort).
• Step 3. Sort the right (using merge sort).
• Step 4. Merge the two sorted sequences.

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;
}