外部quicksort算法讲解
Explanation of external quicksort algorithm
我正在尝试了解快速排序的外部版本（当数据无法装入主内存时）。我找到了外部快速排序过程的following link and similar explanation on Wiki：
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.
我理解有问题：
M是指主存的大小吗？我在某个驱动器上还有 N-M 个元素？
The buffer acts like the pivot in quicksort - 这是否意味着我需要将驱动器中剩余的 N-M 个元素分成两部分 a 和 b，其中a 中的元素低于缓冲区中的所有元素并且 b 中的元素大于或等于缓冲区中的最大元素？
Read the next element from the beginning or end to balance writing.平衡写作是什么意思？应该从缓冲区（内存）还是从驱动器读取下一个元素？
Otherwise write the greatest or least of the buffer, and put the next element in the buffer - 如果我将下一个元素放入缓冲区（已经排序），我需要再次对缓冲区进行排序吗？
一些示例如何工作或更好的解释将非常有用。
注意 - 我不知道有任何库使用快速排序进行外部排序，所以这主要是一个教育练习。
wiki 文章提到了磁带，但这是错误的。不可能在合理的时间内读取磁带上的两个 "ends" 数据，并且不可能在不破坏数据之后的现有数据的情况下覆盖磁带上的数据。因此，请将其视为硬盘驱动器或 SSD 类型设备上文件的外部排序，具有随机访问和就地覆盖数据的能力。
Is M refering to the size of main memory?
根据上下文，工作内存区域的大小为M·sizeof(element)。需要有额外的可用内存才能在不覆盖缓冲区的情况下读取元素。
'N-M` elements on some drive?
是的，因为内存只能放M个元素，所以N-M个元素留在外接设备上。
The buffer acts like the pivot in quicksort?
缓冲区被排序为单个运行，缓冲区中的最小值和最大值加上刚刚读取的一个元素作为一个枢轴值范围，以确定写入哪个元素。
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?
文件开头或结尾有space个要写入M/2个元素。可以从任一端读取第一个元素读取。如果从头开始读取一个元素+M/2。然后缓冲区中最小的元素从头开始写入，仍然留下 M/2 space 用于要写入的元素。如果从末尾读取元素 - M/2，则将最大元素写入文件中的最后一个元素，在末尾留下 M/2 space 用于要写入的元素。
此时算法有问题。每读取一个元素，都需要合并到M个元素的缓冲区中，非常慢。解决此问题的一种方法是为缓冲区使用最小-最大堆。
https://en.wikipedia.org/wiki/Min-max_heap
最终从两端开始写入文件，在中间的M个元素处相遇，然后写入M个元素缓冲区。此时，文件开头的所有元素都小于或等于文件结尾的所有元素，文件可以认为是2个分区。然后对每个分区进行分区，产生 4 个分区，然后 8 个分区，依此类推，直到最终一个分区适合内存并使用正常的内存排序。
所描述的算法很慢，因为它一次读取和写入一个元素。预留一部分内存来缓冲分组读写会快很多。
我正在尝试了解快速排序的外部版本（当数据无法装入主内存时）。我找到了外部快速排序过程的following link and similar explanation on Wiki：
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.
我理解有问题：
M是指主存的大小吗？我在某个驱动器上还有N-M个元素？The buffer acts like the pivot in quicksort- 这是否意味着我需要将驱动器中剩余的N-M个元素分成两部分a和b，其中a中的元素低于缓冲区中的所有元素并且b中的元素大于或等于缓冲区中的最大元素？Read the next element from the beginning or end to balance writing.平衡写作是什么意思？应该从缓冲区（内存）还是从驱动器读取下一个元素？Otherwise write the greatest or least of the buffer, and put the next element in the buffer- 如果我将下一个元素放入缓冲区（已经排序），我需要再次对缓冲区进行排序吗？
一些示例如何工作或更好的解释将非常有用。
注意 - 我不知道有任何库使用快速排序进行外部排序，所以这主要是一个教育练习。
wiki 文章提到了磁带，但这是错误的。不可能在合理的时间内读取磁带上的两个 "ends" 数据，并且不可能在不破坏数据之后的现有数据的情况下覆盖磁带上的数据。因此，请将其视为硬盘驱动器或 SSD 类型设备上文件的外部排序，具有随机访问和就地覆盖数据的能力。
Is
Mrefering to the size of main memory?
根据上下文，工作内存区域的大小为M·sizeof(element)。需要有额外的可用内存才能在不覆盖缓冲区的情况下读取元素。
'N-M` elements on some drive?
是的，因为内存只能放M个元素，所以N-M个元素留在外接设备上。
The buffer acts like the pivot in quicksort?
缓冲区被排序为单个运行，缓冲区中的最小值和最大值加上刚刚读取的一个元素作为一个枢轴值范围，以确定写入哪个元素。
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?
文件开头或结尾有space个要写入M/2个元素。可以从任一端读取第一个元素读取。如果从头开始读取一个元素+M/2。然后缓冲区中最小的元素从头开始写入，仍然留下 M/2 space 用于要写入的元素。如果从末尾读取元素 - M/2，则将最大元素写入文件中的最后一个元素，在末尾留下 M/2 space 用于要写入的元素。
此时算法有问题。每读取一个元素，都需要合并到M个元素的缓冲区中，非常慢。解决此问题的一种方法是为缓冲区使用最小-最大堆。
https://en.wikipedia.org/wiki/Min-max_heap
最终从两端开始写入文件，在中间的M个元素处相遇，然后写入M个元素缓冲区。此时，文件开头的所有元素都小于或等于文件结尾的所有元素，文件可以认为是2个分区。然后对每个分区进行分区，产生 4 个分区，然后 8 个分区，依此类推，直到最终一个分区适合内存并使用正常的内存排序。
所描述的算法很慢，因为它一次读取和写入一个元素。预留一部分内存来缓冲分组读写会快很多。