Menu
Please, provide code examples in a language of your choice.
Update: No constraints set on external storage.
Example: Integers are received/sent via network. There is a sufficient space on local disk for intermediate results.
762
If it's meant as speed, the radix sort is the fastest theoretical sort for this. Especially as we know that the integers are 32bit and thus can only be in a range of values.
1 million 32-bit integers = 4 MB of memory.
Suppose we have to sort a 1GB file of random integers and the available ram size is 200 Mb, how will it be done? The easiest way to do this is to use external sorting. We divide our source file into temporary files of size equal to the size of the RAM and first sort these files.
Read 1 GB of the data in main memory and sort by using quicksort. Write the sorted data to disk. Repeat steps 1 and 2 until all of the data is in sorted 1GB chunks (there are 10 GB / 1 GB = 10 chunks), which now need to be merged into one single output file.
Split the problem into pieces small enough to fit into available memory, then use merge sort to combine them.
66
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
