수억개의 자연수의 정렬

프로그래밍 하는데 질문 있어서 올립니다.
 
123 532 6452 12315 12 14 2 ...\n (파일에 한 라인에 있는거임)
 
이런식으로 자연수가 수억개정도 있는데요.
 
1. 이것을 동적배열로 만들어서 머지 소트할라구 하는데요.
수억개정도 자연수가 있으면 동적할당 하면 메모리용량만 크면 뻑은 안나나요?
 
2. 개행 나오기전까지  strtok으로 짤라서, 짜르면서 배열에 저장하고 싶은데....
그렇게 되면 저 자연수들이 몇개나 있는지 몰라서..
동적배열의 크기를 맘대로 지정할수도 없고..
 
3. 어떤방식으로하면 저것의 개수를 셀수 있을까요?
 
4. 수억개가 있기때문에 한번에 저장안해도 되는데 천만개씩 저장해도 되거든요?
어떤 한변수 동적배열에..그리고 프리하고 다시 거기다가 또 할당하고 이런식이요..
 
그렇게되면 또 개수를 모르게 되면 천만개 했는데 한줄에 300개의 자연수가 있었다면,
나머지 초기화하는데 메모리가 아까운데 해결할 방법좀요~
 
5. 즉 \n까지 체크하고 싶은데 인트형으로 %d로 받아서 if(que[i]=='\n') 이런식으로 쓰면
문제점이 10이면 알아서 이프문 들어가기떄문에 문제가 생기네요....

개행이 아스키 코드값과 일치하면 이프믄 들어가기 때문에...........
 
즉, 저가 모르고 있는 함수나 가저다가 쓸수 있는 함수라도 있으면 알려주세용
 
===========================================================================

#include <stdio.h>
#define SIZE 10000
int main() {
    FILE* fin;
    int x;
    int mydata[SIZE];
    int i=-1;
    char ch;

    fin=fopen("data.txt","r");
 
    while(!feof(fin)) {
        while(fscanf(fin,"%d",&x)!=EOF) {
            // printf(" %d ",x);
            mydata[++i]=x;
            fscanf(fin, "%c", &ch);
 
            if(i>=SIZE) break;
 
        } // 메모리내에서 다룰수 있는 SIZE를 미리 알아 보아야 한다.
          //mergesort(mydata, i); // 머지 소트부분은 생략함, 가장큰 갯수로 SIZE를 정해준다.
          //savetofile(mydata, i);  // 적당한 파일 이름을 주어서 저장한다.
          // 나중에 불러올때 필요한 파일이름을 알수 있어야 한다.
    }
    fclose(fin);
 
    // 두개의 파일을 열고 머지를 한다음 한개의 파일에 저장한다.
    // 위의 경우 머지소트를 하는 부분이 모두 메모리 내에서 이루어 진다는 것이다.
    // 지금은 파일1, 파일2 읽어서 파일3으로 출력하는 것이다.
    // 위의 과정을 되풀이 하여 처음에 주어진 파일들을 모두 머지한다.
 
    // 이제 위의 과정에서 주어진 파일들을 마찬가지 방법으로 머지한다.
 
    // 이런 과정을 되풀이 하여 한개의 파일이 남을 때 까지 되풀이 한다.
    return 0;
 }
 
===================================================================================
보디 획기적인 방법이 있다. 만약 자연수의 범위가 32비트로 표현하는 양수의 범위
안에 있다면 각 자연수들을 인덱스로 하여
 
int mydata[2^31] // 2의 31승개 만큼의 배열을 잡아준다. 그리고 모두 0으로 초기화한다.
위에서 읽은 x를 이용하여 mydata[x]++; 이라고 해주면 된다.
 
여기서 문제는 이렇게 큰 배열을 메모리 내에 잡을 수가 없다는 것이다.
이 문제는 랜덤으로 읽고 쓸수 있는 파일을 만들어서 파일에 직접 쓰는 방법이 있다.
 
=================================================================================
 
이 방법을 조금더 개선하면 위의 배열을 적당한 크기로 잘라서 메모리 안에 둘수 있는
크기를 구해본다
 
예를들어서 배열의 크기가 천만까지는 메모리 내에 허용이 될수 있을것이다.
2^31을 천만으로 쪼개면 21개 정도의 쪼개진 배열이 필요하다.
 
자 원래의 파일을 읽으면서 자연수의 범위에 따라서 21개의 파일에 각각 순차적으로
write를 한다. 그러면 각각의 파일은 범위내의 자연수들을 포함하고 있을 것이다.
 
이들 파일에 있는 자료의 갯수는 중요하지 않다.
중복된 자료가 2^31개 내이기만 하면 되는 것이다.
 
이제 원래 파일을 21개의 파일로 쪼갯다.
 
순서대로 파일을 읽고는 위에서 이야기한 방법으로 갯수를 센다. 모두 메모리 내에서
이루어 진다. 한개의 파일을 다 읽고 나면 바로 이 배열을 최종출력파일에 출력한다.
 
위의 과정을 21개 파일에 대하여 되풀이 한다. 그러면 최종출력파일은 모든 자료가
정렬된 상태로 되어 있을 것이다.
 
==================================================================================
 
주어진 자연수가 32비트로 표현할수 없는 큰 경우: 예를 들어서 64비트로 표현된 경우
에는 위의 방법을 응용해 본다.
 
전체 자연수의 구간을 십만개 정도로 세분하여 배열에 그 갯수를 더해본다.
전체 파일을 읽으면서 파일에 있는 자연수의 분포를 알아 낼수 있다.
 
이 분포를 이용하여 원래의 파일을 크기가 비슷한 100개의 파일로 쪼갤수가 있다.
 
이 주어진 파일들은 충분히 작기 때문에 쉽게 정렬할 수가 있다.
 
이들 100개의 파일에 대해서 정렬 최종파일에 출력을 되풀이 하면 우리가 원하는
결과 파일을 구할수가 있다.