在某些应用中，因为内存资源有限制，而要排序的文件很大（比如10G的文件，只有10M的内存）

主要的思想是：

1 分割文件，使分割的文件能全部加载到内存。

2 分别排序每一个分割的文件

3 合并文件

 

难的是合并操作

1 跌增合并，一次合并两个文件。依次类推，直到最终只剩一个文件。时间复杂度主要在读取文件，要多次读取。

2 利用堆，一次合并多个文件  时间复杂度主要取决于堆的查找。（堆主要用于查找当前最小的行）

   或者更直接的是，每次顺序查找当前内存中的最小行。

 

一般而言内存访问速度要快很多，因此第2中方法应该快很多。

如下是一个简单的window上的实现：

//单行最大长度lEN_LINE - 1 #define LEN_LINE 80 int cmp(const void * str1, const void *str2) {
    const char *p1 = (char *)str1, *p2 = (char *)str2; return strcmp(p1, p2); } /*     文本文件以行为单位排序 */ bool FileSort(const char *file, size_t memLimit) {
        FILE *fp;     fp = fopen(file, "r");     fseek(fp, 0, SEEK_END);     size_t file_size = ftell(fp);     fseek(fp, 0, SEEK_SET);     size_t split_cnt = (file_size+memLimit-1)/memLimit; char prefix[256] = "tttt"; char file_t[256]; int fileNo; //临时文件编号     char *buff = new char[memLimit]; if (buff == NULL) return false;     size_t totalReadLen=0;                //已读文件大小      size_t lineCnt = memLimit/LEN_LINE;    //分配的空间能存下的行数     fileNo = 1; //分割文件并排序     while (totalReadLen < file_size)     {
    //生成一个临时文件名         sprintf(file_t, "%s%d.txt", prefix, fileNo);         FILE *fp_t = fopen(file_t, "w");         size_t read_len=0; int i=0; //按行读取         while ( (i
      
       0)                 min = i;         } if (buff[min*LEN_LINE])         {
                fputs(buff+min*LEN_LINE, fp);             flg[min] = true;         } else break;            }     fclose(fp); return true; }