Re: Simple disk-based sorting method

David Kelly wrote:
> Citizen Bob wrote:
>>>
>>> An easy way to solve your problem is to just open the source file and 
>>> bite off as much as you can sort in memory.
>>>
>>> Sort it. And write an output file.
>>>
>>> Take another bite, sort, and write to a different output file.
>>>
>>> Repeat until the entire original file has been bitten off and written 
>>> to smaller (but internally sorted) tem****ary files.
>>>
>>> Now open all the tem****ary output files. Read the first record from 
>>> each. Write to your final output file the one record which sorts 
>>> first. Replenish it with the next record from the file it came from. 
>>> Repeat until all records in the tem****ary files have been copied to 
>>> the output file.
>>>
>>> If you end up with 1,000 output files and can not open all at once, 
>>> bite off as many as you can, say 20, and merge them into a single 
>>> file, and another 20. And then merge the merged files, generation 
>>> after generation, until you are down to a single file.
>>
>> I chose the Radix Sort and it works beautifully. I only have to open
>> 11 files at a time - the input or the output file and 10 tem****ary
>> files. I discover the digit value in the key and use it as an index
>> into an array of FILE pointers.
>>
>> FILE *fp_temp[10];
>> fprintf(fp_temp[key],"%s",record);
> 
> Whatever floats your boat. But I think what you describe is clumsy and 
> only barely works in the specific application you describe. Grow the 
> application and it will break as your solution is delicate.
> 
> You are counting on an even distribution of the data which is already 
> too large to handle in memory (doesn't matter what you use to sort in 
> memory). You are counting on being able to break it into only 10 
> segments based on a pattern, and that none of those segments will be too

> large to handle in memory.
> 
> Your first pass deals the data into 10 different files. Your 2nd pass 
> loads each file in memory to perform the actual sort. Then 3rd pass 
> concatenates the files into one.
> 
> What I suggested was to take as much as you can and sort it, then write 
> a tem****ary file. Repeat until all data is now in multiple tem****ary 
> files, the contents of each is sorted. Then open all of these files and 
> your first data record will be the first data record from one of those 
> files. Each tem****ary file is now ordered so your final sort only has to

> compare the current record from each.
> 
> If you have more tem****ary files than you can open simultaneously then 
> the procedure can recurse, merging tem****ary files until a single file 
> remains.
> 
> If you like having names for things, splitting into multiple sorted 
> files and putting them back together is called a merge sort.
The thing about sorting numbers is you can sort from highest to lowest 
and just write the file and then append to the end of the file.