Progressive sorting in the external memory model

Executing all steps of an algorithm that faces with massive input data may take a long time. A progressive algorithm solves the problem step by step, and produces a partial solution in each step which approximates the final solution. Therefore, the user can decide to stop the algorithm or continue to get better solutions. In this paper, we consider the problem of sorting a set of N real numbers, and design a progressive algorithm with 𝑂(log𝑀/𝐵𝑁/𝐵) steps that takes 𝑂(𝑁/𝐵) I/O operations in each step in the external memory model. The upper bound for the error of the partial solution in step r is 𝑂(𝑁(𝑀/𝐵)𝑟/2).