External sorting
Sort strategy
Merge strategy
With some example
External sorting is a sorting technique used for large datasets that cannot fit entirely in memory. It involves reading chunks of data from disk, sorting them in memory, and then merging the sorted chunks to obtain the final sorted dataset.
The sort strategy in external sorting typically involves the following steps:
1. Divide the dataset into smaller chunks that can fit in memory.
2. Read each chunk into memory and sort it using an internal sorting algorithm like quicksort or merge sort.
3. Write the sorted chunk back to disk.
4. Repeat steps 2 and 3 until all chunks have been sorted and written to disk.
5. Perform a merge step to combine the sorted chunks and obtain the final sorted dataset.
The merge strategy in external sorting involves merging the sorted chunks generated during the sort phase. There are different approaches to merging, including two-way merge, k-way merge, and polyphase merge.
Example: Let's say we have a dataset of 1 billion records, and our available memory can only hold 100 million records at a time. We can perform external sorting using the following steps:
1. Divide the dataset into 10 chunks, each containing 100 million records.
2. Read the first chunk into memory, sort it using an internal sorting algorithm, and write it back to disk as a sorted chunk.
3. Repeat step 2 for the remaining chunks until all 10 chunks have been sorted and written to disk.
4. Perform a two-way merge by reading the first two sorted chunks into memory, comparing the records, and writing the smaller records to a new sorted chunk on disk.
5. Continue the merge process by reading the next pair of sorted chunks, comparing records, and writing to a new sorted chunk until all the sorted chunks have been merged into a single sorted dataset.
By dividing the sorting process into smaller chunks and merging them gradually, external sorting allows us to deal with large datasets that cannot fit in memory. This technique is commonly used in scenarios such as sorting database tables or processing large log files.