File ExternalSorting.h

↰ Parent directory (ADS/external)

The sort of n atomic items in the two-level memory [see File TwoLevelMemory.h], by merging and by distribution, with the lower bounds that make both optimal, written as functions that a test can compare with the I/Os counted.

Definition (ADS/external/ExternalSorting.h)

Detailed Description

  • binaryMergeSort() cuts the input in runs of :math:` R = lfloor M / B rfloor B ` items, sorted in memory (the recursion of the mergesort stopped where the subsequence fits, which saves its :math:` log_2 M ` lowest levels), and then merges the runs two by two, three blocks of memory; each pass reads and writes every block once, hence at most :math:` 2 lceil n / B rceil ( 1 + lceil log_2 ( n / R ) rceil ) ` I/Os, mergeSortIOs() with k = 2.

  • multiwayMergeSort() merges :math:` k = M / B - 1 ` runs at a time, a block per run and one for the output, the minimum chosen by a tree of losers [see File LoserTree.h] or by any structure with its interface (a parameter, so that the same algorithm runs on the trees and the heaps of Namespace ADS and of the other libraries, with the same I/Os), so that the passes drop to :math:` lceil log_k ( n / R ) rceil ` and the I/Os to :math:` O( ( n / B ) log_{M / B} ( n / M ) ) ` (Theorem 5.1 of the notes), which is optimal. With snowPlow the runs are made by replacement selection, the snow plow of Knuth [see replacementSelection() of File ExternalSort.h, the same runs in memory], a heap of M - 2 B items that gives runs of 2 M items on average on a random input and a single run on a sorted one.

  • sortingLowerBound() is the bound of Aggarwal and Vitter by the tree of the I/Os: a read of B items into a memory that holds M - B others can have at most :math:` binom{M}{B} ` outcomes, times :math:` B! ` when the B items are read for the first time, and the leaves must be at least n!; the smallest t with :math:` binom{M}{B}^t ( B! )^{lceil n / B rceil} geq n! ` bounds the reads, :math:` t = Omega( ( n / B ) log_{M / B} ( n / M ) ) , and the output adds its :math: lceil n / B rceil ` writes. permutingLowerBound() counts also the writes, each of which can go to n + 1 places: :math:` ( ( n + 1 ) binom{M}{B} )^t ( B! )^{lceil n / B rceil} geq n! , which gives :math: Omega( min{ n , ( n / B ) log_{M / B} ( n / M ) } ) ` (Theorem 5.4): moving the items, not finding their order, is the cost of a sort on the disk.

  • permuteBySorting() is the algorithm of Theorem 5.2: the pairs :math:` langle i , pi( i ) rangle ` sorted by :math:` pi( i ) `, a coordinated scan with the input that fills in the items, a sort back by i, two sorts and three scans; permuteDirect() moves one item per read, up to n reads, better only when B is below the logarithm of the sort.

  • distributionSort() is the multiway quicksort of section 5.3.4: k - 1 pivots taken from a sample of :math:` ( a + 1 ) k - 1 ` random items, :math:` a + 1 = lceil 12 ln k rceil ` (Algorithm 5.7 and Lemma 5.1: with probability at least 1/2 every bucket gets fewer than 4 n / k items, else the sample is drawn again, at most twice), the items distributed by one scan into the buckets between the pivots and into one bucket per pivot for the items equal to it (the three-way partition of section 5.3.1, so that equal keys stop the recursion), and the buckets sorted in turn, in memory once they fit. The memory holds the input block, the 2 k - 1 blocks of the buckets, the block of the output and the pivots, hence :math:` k = lfloor ( M - B ) / ( 2 B + 1 ) rfloor , half the fan-in of the merge, and the same :math: O( ( n / B ) log_{M / B} ( n / M ) ) ` I/Os on average.

Compared with the literature: the merge with a tree of losers is the standard of the external sorters (Knuth 5.4.1, the STXXL library of Dementiev, Kettner and Sanders), the distribution with oversampling the sample sort of Frazer and McKellar, here as in the analysis of Vitter’s survey; on D disks the striping turns either into a sorter with blocks of D B items, :math:` O( ( n / D B ) log_{M / D B} ( n / M ) ) , which loses a factor :math: 1 - log_{M / B} D ` in the base of the logarithm, and Greed Sort of Nodine and Vitter recovers the optimum (section 5.4, not simulated here: one disk is the model of these functions). The items of the model are atomic: a pair or a triple counts as one item.

The contracts [see File Contract.h]: :math:` M geq 3 B ` for the merges and :math:` M geq 5 B + 2 ` for the distribution; the files share the memory, the output file is empty; the output holds the items of the input, sorted, an audit; pi is a permutation of 0 , … , n - 1, an audit. The functions are defined in ExternalSorting.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 5

  1. Aggarwal, J. S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM 31(9), 1116-1127, 1988, doi:10.1145/48529.48535

    1. Knuth, The Art of Computer Programming, vol. 3, 2nd ed., Addison-Wesley, 1998, sections 5.4.1 and 5.4.9

    1. Frazer, A. C. McKellar, Samplesort: a sampling approach to minimal storage tree sorting, Journal of the ACM 17(3), 496-507, 1970, doi:10.1145/321592.321600

    1. Nodine, J. S. Vitter, Greed Sort: optimal deterministic sorting on parallel disks, Journal of the ACM 42(4), 919-933, 1995, doi:10.1145/210332.210337

  1. Dementiev, L. Kettner, P. Sanders, STXXL: standard template library for XXL data sets, Software: Practice and Experience 38(6), 589-637, 2008, doi:10.1002/spe.844

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Functions