I'm trying to understand external version of quicksort (when the data cannot be fited into main memory). I found the following link and similar explanation on Wiki of external quicksort procedure:
Definition: Read the M/2 first and last elements into a buffer (the buffer acts like the pivot in quicksort), and sort them. Read the next element from the beginning or end to balance writing. If the next element is less than the least of the buffer, write it to available space at the beginning. If greater than the greatest, write it to the end. Otherwise write the greatest or least of the buffer, and put the next element in the buffer. Keep the maximum lower and minimum upper keys written to avoid resorting middle elements that are in order. When done, write the buffer. Recursively sort the smaller partition, and loop to sort the remaining partition.
I have problems to understand it:
Is M refering to the size of main memory? And I have remaining N-M elements on some drive?
The buffer acts like the pivot in quicksort - does this mean that I need to partition remaining N-M elements from the drive into two parts a and b, where elements from a are lower than all elements from buffer and elements from b are greater or equal to the maximum element from buffer?
Read the next element from the beginning or end to balance writing. What does it mean to balance writing? Should next element be read from the buffer (memory) or from the drive?
Otherwise write the greatest or least of the buffer, and put the next element in the buffer - if I put next element into buffer (which is already sorted) I need to sort the buffer again?Some example how it works or better explanation would be very useful.
Note - I'm not aware of any library that uses quicksort for external sorting, so this is mostly an educational exercise.
The wiki article mentions magnetic tape, but this is wrong. It's not possible to read from both "ends" of data on a magnetic tape in a reasonable amount of time, and it's not possible to overwrite data on tape without destroying existing data that is just after the data. So instead consider this to be an external sort for a file on a hard drive or SSD type device with random access and the ability to overwrite data in place.
Is
Mrefering to the size of main memory?
Based on the context, the size of working memory area is M · sizeof(element). There needs to be additional available memory to read in an element without overwriting the buffer.
'N-M` elements on some drive?
Yes, since memory can only hold M elements, then N-M elements remain on the external device.
The buffer acts like the pivot in quicksort?
The buffer is sorted into a single run, and the smallest and largest values in the buffer plus the one element just read act as a range of pivot values, to determine which element to write.
Read the next element from the beginning or end to balance writing.` What does it mean to balance writing? Should next element be read from the buffer (memory) or from the drive?
There is space to write M/2 elements at the beginning or end of the file. The first element read can be read from either end. If an element is read from the beginning + M/2. then the smallest element in the buffer is written at the beginning, still leaving M/2 space for elements to be written. If an element is read from the end - M/2, then the largest element is written at the last element in the file, leaving M/2 space at the end for elements to be written.
Problem with the algorithm at this point. As each element is read, it needs to be merged into the buffer of M elements, which is very slow. One solution to this issue would be to use a min-max heap for the buffer.
https://en.wikipedia.org/wiki/Min-max_heap
Eventually the file is written starting at both ends meeting at the middle M elements, where the M element buffer is then written. At this point, all the elements on the beginning side of the file are less than or equal to all of the elements on the ending side of the file and the file can be considered as 2 partitions. Then each partition is partitioned, resulting in 4 partitions, then 8 partitions, and so on, until eventually a partition fits in memory and a normal memory sort is used.
The algorithm as described is slow, since it reads and writes one element at at time. It would be much faster to reserve part of memory to buffer reads and writes in groups.