10G大小的数组只用100M内存进行排序计算

先讲下大致思路：

1、把数组分成n =ceil(arr_size/mem_size) 个小数组，分别对每个小数组排序（只能用冒泡、插入等空间复杂度是O(1)的排序方法）（实际写入n个文件）

2、依次从n个数组（实际应从文件中读取）中取出一个值，把最小的值放入输出的数组中，直到输出的数组增长mem_size长度之后（达到内存上限，写入磁盘），然后进行下一轮循环

function insertSort($arr) {
    $n=count($arr);
    for($i=1;$i<$n;$i++) {
        $tmp=$arr[$i];
        $j=$i-1;
        while($arr[$j]>$tmp) {
            $arr[$j+1]=$arr[$j];
            $arr[$j]=$tmp;
            $j--;
            if($j<0)
                break;
        }
    }
    return $arr;
}
function sorts($from_file_arr,$mem_size,$method = 'insert'){
    #$method = 'insert';
    $fun = $method.'Sort';
    $arr_size = count($from_file_arr);
    $to_file_arr = [];
    if($mem_size < $arr_size){
        $arr_num = ceil($arr_size/$mem_size);
        //模拟分段读取文件
        for($i = 0; $i<$arr_num; $i++){
            $tmp_arr = [];
            $start = $i*$mem_size;
            $end = ($i+1)*$mem_size;
            if(($i+1) == $arr_num) $end = $arr_size;
            for ($j = $start; $j < $end; $j++){
                array_push($tmp_arr,$from_file_arr[$j]);
            }
            $piece_file_arr[$i] = $fun($tmp_arr);//这里模拟写入文件piece_file_$i.txt
        }
        //模拟输出到文件
        $pointer = array_fill(0,$arr_num,0);
        $white_list = [];
        for($i = 0; $i < $arr_num; $i++){
            array_push($white_list,$i);
        }
        $finished_list = [];
        for($i = 0; $i < $arr_num; $i++){
            $start = $i*$mem_size;
            $end = ($i+1)*$mem_size;
            if(($i+1) == $arr_num) $end = $arr_size;

            for($j = $start; $j < $end; $j++){
                $left_list = array_diff($white_list,$finished_list);
                $line = reset($left_list);
                $tmp_val = $piece_file_arr[$line][$pointer[$line]];
                for($k = 0; $k < $arr_num; $k++){
                    if(in_array($k,$finished_list)){
                        continue;
                    }
                    if(isset($piece_file_arr[$k][$pointer[$k]])){
                        if($piece_file_arr[$k][$pointer[$k]] < $tmp_val){
                            $tmp_val = $piece_file_arr[$k][$pointer[$k]];
                            $line = $k;
                        }
                    }
                }
                $pointer[$line]++;
                if($pointer[$line] == $mem_size){
                    array_push($finished_list,$line);
                }
                $to_file_arr[$j] = $tmp_val;//这里模拟写入最终的文件to_file.txt
            }
        }
        return $to_file_arr;
    }else{
        return $fun($from_file_arr);
    }
}
/*
 * 数组模拟文件中的数据
 * $from_file_arr  未排序的文件
 * $piece_file_arr  分成小块的文件
 * $to_file_arr  已排序的文件
 * $mem_size 约束的内存大小
 */
$from_file_arr = [5,1,0,3,2,4,8,6,9,7,10,18,13,14,12,16,17,19,11,15,20,29,24,28,25,27,23,26,22,21];
$mem_size = 10;
print_r(sorts($from_file_arr,$mem_size));