Resumen de Adaptive parallel sorting

Vladimir Estivill- Castro , Derick Wood

• The capacity of an algorithm to modify its behavior to the size, difficulty or structure of the problem instance has been named adaptivity. The literature on parallel algorithms qualifies as adaptive those algorithms that work with a fixed amount of processors on input of arbitrary size while the literature on sorting algorithms qualifies as adaptive those algoritms that perform work proportional to the amount of disorder in the input. We combine these two concepts and present the first two parallel sorting algorithms that -are designed for a fixed number of processors and reconfigure according to the size of the input.

  - adapt to the amount of disorder in the input, and -are cost optimal.