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: Divide
        long m=n/2;
        //Step 2: Sort left
        mergeSort(seq,m);
        //Step 3: Sort right
        mergeSort(seq+m,n-m);
        //Step 4: Merge
        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;
}
Problem 1.

The user input consists of an integer n, a sequence x of n integers, and an integer M. Create a program that identifies two terms from the sequence x whose sum is closest to M. If there are several pairs of integers from x whose sum is closest to M, the program can choose any of them. The complexity of the program should be at most \(O(n\log n)\).

Problem 2.

The non-recursive implementation of the merge sort algorithm applied to the sequence x[0], x[1], x[2], \(\dots\) can be divided into steps. In the first steps, the entire sequence is divided into blocks of size \(2\) and each of these blocks is sorted. In the second step, the adjacent blocks of size \(2\) are merged and the new blocks of size \(4\) are obtained. In the step \(3\), the sorted blocks from step \(2\) are now merged into sorted blocks of size \(8\), etc. The user input consists of non-negative integers \(i\) and \(j\). Create the program that determines the step in which the terms \(x[i]\) and \(x[j]\) will end up in the same block for the first time.

Problem 3. Write a program that performs the merge-sort algorithm without using a recursion.