My code should be faster than merge sort but I get no error when I use merge sort but I get timeout error in my code.
here is my algorithm
as i get another element I put it into my array such that array remains sorted
that is I search its position using binary search.
that is log(n) complexity for nth element added
net complexity is log(1)+log(2)+…+log(n)<nlog(n) ie faster than merge sort but it gives timeout error, code gives correct ans for small values so code is correct
while merge sort does not give timeout error here is my code:
#include<stdio.h>
int array[10001000];
int limit=0;
void sortadd(int n)
{
if(limit==0)
{
array[0]=n;
limit++;
return;
}
if(n>=array[limit-1])
{
array[limit]=n;
limit++;
return;
}
int i=0;
if(n<=array[0])
{
for(i=limit;i>0;i–)
{
array[i]=array[i-1];
}
array[0]=n;
limit++;
return;
}
int a=0,b=limit-1,c;
while(b-a>=2)
{
c=(a+b)/2;
if(array[c]==n)
{
for(i=limit;i>c;i–)
{
array[i]=array[i-1];
}
array[c]=n;
limit++;
return;
}
if(array[c]>n)
b=c;
else
a=c;
}
for(i=limit;i>b;i–)
{
array[i]=array[i-1];
}
array[b]=n;
limit++;
return;
}
int main()
{
int lim,n,i,j,k,temp;
scanf("%d",&lim);
if(lim>10001000||lim<=0)
return 0;
for(i=0;i<lim;i++)
{
scanf("%d",&n);
if(n>10001000||n<0)
break;
sortadd(n);
}
for(i=0;i<limit;i++)
{
printf("%d\n",array[i]);
}
return 0;
}