How To increase input size of program

Question

This program takes two input . first Array size(n) and choice ex:- if n is 100 than my program generate 100 random numbers and sort them using merge sort and quick sort.

Now if you enter choice==2 than it display time taken by both sorting algorithm

My program works upto input size 10^8 but I want it to work upto 10"10 .If i enter input size 10^9 it gives segmentation fault . there is problem in allocation that much amount of memory .malloc returns null if input size exceeds 10^9

Can anyone please tell me how can I improve my program's input size...........

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

long long merge(int *A,long long i,long long mid,long long j)                   

{   

int *C;
C=(int *)malloc(sizeof(int)*(j-i+1));                           
long long  r,start,k;
r=0;
start=i;
k=mid+1;
while((i<=mid)&&(k<=j))
{
    if(A[i]>A[k])
    {
        C[r]=A[k];
        r++;k++;
    }
    else
    {
        C[r]=A[i];
        r++;i++;
    }
}
while(i<=mid)
{
    C[r]=A[i];
    r++;i++;
}
while(k<=j)
{
    C[r]=A[k];
    r++;k++;
}
for(i=0;i<r;i++,start++)
    A[start]=C[i];
free(C);
  }
   long long partition(int *A,long long i,long long j)                           
   {

long long mid;
mid=(i+j)/2;                                    
if(i<j)
{
    partition(A,i,mid);                         
    partition(A,mid+1,j);
    merge(A,i,mid,j);                       
}
    }

    long long find_position(int A[],long long i,long long j)                        

    {

long long pivot,temp,end;
end=j;
pivot=i;
while(i<j)
{
    while(A[i]<=A[pivot]&&i<end)
        i++;
    while(A[j]>A[pivot])
        j--;
    if(i<j)
    {
        temp=A[i];
        A[i]=A[j];
        A[j]=temp;
    }
}
temp=A[pivot];
A[pivot]=A[j];
A[j]=temp;
return j;
  } 
  long long quicksort(int A[],long long  i,long long  j)                                
  {
long long position;
if(j>i)
{
    position = find_position(A,i,j);
    quicksort(A,i,position-1);
    quicksort(A,position+1,j);
  }
    }
   int main()
  {
clock_t start,end,quick_sort,merge_sort;
long long input_size,i;
int choice,x;
srand(time(NULL));
printf("Enter input Size\n");
scanf("%lld",&input_size);
int *A,*B;
printf("input your choice\n");
scanf("%d",&choice);
A=(int *)malloc(input_size*sizeof(int));
B=(int *)malloc(input_size*sizeof(int));
if(A==NULL||B==NULL)
{
    printf("sorry that much memory can't be allocated\n");
    return 0;
}
for(i=0;i<input_size;i++)
{
    x=rand();
    A[i]=x;
    B[i]=x;
}
if(choice==1)
{
    printf("Array entered by user\n");
    for(i=0;i<input_size;i++)
        printf("%d  ",A[i]);
}
start=clock();
partition(A,0,input_size-1);
end=clock();
merge_sort=end-start;
if(choice==2)
    printf("\n time taked by merge sort is %6.6f",((double)(merge_sort)/CLOCKS_PER_SEC));
if(choice==1)
{
    printf("\nmerge sorted array\n");
    for(i=0;i<input_size;i++)
        printf("%d  ",A[i]);
}
start=clock();
quicksort(B,0,input_size-1);
end=clock();
quick_sort=end-start;
if(choice==2)
    printf("\n time taked by quick sort is %6.6f",((double)(quick_sort)/CLOCKS_PER_SEC));
if(choice==1)
{
    printf("\nquick sorted array\n");
    for(i=0;i<input_size;i++)
        printf("%d  ",B[i]);
}
printf("\n");
return 0;

}

Answer 1

The max allocatable size is 2GB for malloc(which takes size_t). Hence your program crashes. I am assuming you're on a 32 bit machine.

Please see below link to learn more about it and test if you can actually allocate that much memory.

How Big can a malloc be in C

To get around this, you will need to write your own VIRTUAL MEMORY MANAGER and MEMORY ALLOCATOR using binary files and write your own free() and malloc() routines.

See here for an example(this is for iPhones only): Create your own VMM

Answer 2

You need to take into account that the address range can be 32bit or 64 bit and some of that is required for the stack, other variables, housekeeping etc. In addition many (all?) OS have soft and hard limits to prevent a process soaking up all the physical and swap memory.

Anyway why are you doing this?