1. External Sorting

1.1. External Sorting

Problem: Sorting data sets too large to fit into main memory.
- Assume data are stored on disk drive.
To sort, portions of the data must be brought into main memory, processed, and returned to disk.
An external sort should minimize disk accesses.

Secondary memory is divided into equal-sized blocks (512, 1024, etc…)
A basic I/O operation transfers the contents of one disk block to/from main memory.
Under certain circumstances, reading blocks of a file in sequential order is more efficient. (When?)
Primary goal is to minimize I/O operations.
Assume only one disk drive is available.

Often, records are large, keys are small.
- Ex: Payroll entries keyed on ID number
Approach 1: Read in entire records, sort them, then write them out again.
Approach 2: Read only the key values, store with each key the location on disk of its associated record.
After keys are sorted the records can be read and rewritten in sorted order.

Quicksort requires random access to the entire set of records.
Better: Modified Mergesort algorithm.
- Process \(n\) elements in \(\Theta(\log n)\) passes.
A group of sorted records is called a run.

Split the file into two files.
Read in a block from each file.
Take first record from each block, output them in sorted order.
Take next record from each block, output them to a second file in sorted order.
Repeat until finished, alternating between output files. Read new input blocks as needed.
Repeat steps 2-5, except this time input files have runs of two sorted records that are merged together.
Each pass through the files provides larger runs.

Is each pass through input and output files sequential?
What happens if all work is done on a single disk drive?
How can we reduce the number of Mergesort passes?
In general, external sorting consists of two phases:
- Break the files into initial runs
- Merge the runs together into a single run.

General approach:
- Read as much of the file into memory as possible.
- Perform an in-memory sort.
- Output this group of records as a single run.

Break available memory into an array for the heap, an input buffer, and an output buffer.
Fill the array from disk.
Make a min-heap.
Send the smallest value (root) to the output buffer.

If the next key in the file is greater than the last value output, then
- Replace the root with this key
else
- Replace the root with the last key in the array
Add the next record in the file to a new heap (actually, stick it at the end of the array).

Saving...

Server Error
Resubmit

Imagine a snowplow moving around a circular track on which snow falls at a steady rate.
At any instant, there is a certain amount of snow S on the track. Some falling snow comes in front of the plow, some behind.
During the next revolution of the plow, all of this is removed, plus 1/2 of what falls during that revolution.
Thus, the plow removes 2S amount of snow.

Simple Mergesort: Place runs into two files.
- Merge the first two runs to output file, then next two runs, etc.
Repeat process until only one run remains.
- How many passes for r initial runs?
Is there benefit from sequential reading?
Is working memory well used?
Need a way to reduce the number of passes.

Saving...

Server Error
Resubmit

Larger files will need more passes – but the run size grows quickly!
This approach trades (\(\log b\)) (possibly) sequential passes for a single or very few random (block) access passes.
Example: use 1/2 MB of working memory
- Average run size from Replacement Selection is 1MB
- Merge 128 runs in one multi-way merge pass (blocks are 4096 bytes each)
- This would be 128MB in 2 passes (if records have a 4-byte key and 4-byte data field, that would be 16 Million records).
- 3 passes would be enough for any conceiveable practical application.
- Or, use some more memory: 1MB of memory would allow for for a 1/2 GB file to be processed in 2 passes. 2MB of memory would be 2GB.

A good external sorting algorithm will seek to do the following:
- Make the initial runs as long as possible.
- At all stages, overlap input, processing and output as much as possible.
- Use as much working memory as possible. Applying more memory usually speeds processing.
- If possible, use additional disk drives for more overlapping of processing with I/O, and allow for more sequential file processing.

Regardless of your views on the politics of energy use and the effect of climate change, some things are not debatable:
- Computers, collectively, use a LOT of power.
- Data Centers are controversial because they compete with people’s access to resources.
  - Electricity, water
- Electricity costs money. Companies would prefer not to waste their money.