1 Introduction to C++ 2 Variables, branching, and loops 3 Functions and recursions 4 Pointers 5 Linked lists 6 Stacks 7 Sequences 8 Pointers practice 9 References 10 Merge sort 11 Object oriented programming 12 Trees in C++ 13 Balanced trees 14 Sets and maps: simplified 15 Sets and maps: standard 16 Dynamic programming 17 Multi core programming and threads 18 Representation of integers in computers 19 Floating point representation 20 Templates 21 Inheritance

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

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, x, x, $$\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.