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: 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; }
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)\).
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.