Lecture Notes: Permutation in External Memory

In this lecture, we will study the permutation problem. The input is an array A1 of size n where the i-th cell (1 ≤ i ≤ n) is a pair (ei, pi). We refer to ei as an element, which fits in one word but its contents are of no interest to us. The second field pi is an integer from 1 to n such that the values of p1, p2,..., pn are distinct. The goal is to output another array A2 of n elements where ei is placed at the pi-th position (note that ei was in the i-th cell of A1). In RAM, we can easily solve the problem optimally in O(n) time: for each i ∈ [1, n], set A2[pi] = ei. The problem is far more interesting in EM, where A1 is given to us in O(n/B) blocks, and we need to output A2 also in O(n/B) blocks. There are two obvious solutions. The first one is to sort the elements e1,..., en by their designated positions p1,..., pn; the cost is O((n/B) logM/B(n/B)) I/Os. The second solution is to simply ignore blocking, and apply the RAM algorithm directly; the cost is O(n), because writing to each position of A2 may cost us an I/O. A natural question arises—since it is possible to achieve linear cost (i.e., O(n)) in RAM, is it possible to achieve linear cost (i.e., O(n/B)) in EM? This is one of the biggest open problems in EM. What is known is that this is impossible for an important class of algorithms that obey the so-called indivisibility assumption (both the naive solutions mentioned earlier are in this class)