Merge Sort showing TLE

#1

question–>
https://practice.geeksforgeeks.org/problems/merge-sort/1#

code–>
void merge(int arr[], int l, int m, int r)
{
int i=l;
int j=m+1;
int k=l;

 int  temp[100001]={0};
 while(i<=m and j<=r){
     if(arr[i]>arr[j]){
         temp[k++]=arr[j++];
     }
     else{
         temp[k++]=arr[i++];
     }
 }
 while(i<=m){
     temp[k++]=arr[i++];
 }
 while(j<=r){
     temp[k++]=arr[j++];
 }
 int c=0;
 for(int i=l;i<=r;i++){
     arr[i]=temp[i];
     c++;
 }

}
it is showing TLE help!!

#2

Hey @sheikhhaji18

void merge(int arr[], int l, int m, int r)
{
int i=l;
int j=m+1;
int k=0;//start from 0

 int  temp[r-l+1]={0}; //only allocate req space because this also take some time
 while(i<=m and j<=r){
     if(arr[i]>arr[j]){
         temp[k++]=arr[j++];
     }
     else{
         temp[k++]=arr[i++];
     }
 }
 while(i<=m){
     temp[k++]=arr[i++];
 }
 while(j<=r){
     temp[k++]=arr[j++];
 }
 for(int i=l;i<=r;i++){
     arr[i]=temp[i-l];//because started k from 0
 }
}

U can also see this if u want to https://stackoverflow.com/questions/16064820/what-is-the-time-complexity-of-array-initialization#:~:text=In%20theory%2C%20both%20have%20the,could%20be%20done%20through%20memset%20).

#3

thanks @Kartikkhariwal1 allocation and initialization takes time that’s all i need to know,right, i cannot understand from that stackoverflow link ;

#4

Yeah @sheikhhaji18
That’s all you need to know :slight_smile:

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#6

Inversion count
question–>
https://practice.geeksforgeeks.org/problems/inversion-of-array-1587115620/1#
code–>


it is showing segmentation fault!!

#7

Open another doubt for different question :slight_smile:

#8

Hello @sheikhhaji18, there are 3 possible changes you need to do in your code.

  1. Intialise j = mid+1 not j = mid
  2. The formula for calculating inverse must be mid-i+1 not mid-s+1
  3. The return type for the i_c function must be long long int not int (define it like long long int i_c())
    I hope it will be clear to you.
#9

okay i got it thanks

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.