About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Abstract
Sorting algorithms are developed in the setting of iterative multilevel methods. These algorithms borrow aggregation techniques from algorithms used for the numerical solution of elliptic partial differential equations which are of optimal order in running time and storage space for structured problems. A computationally inexpensive preconditioner drives random data chosen from known distributions towards a special case for which the new sorting algorithms are of optimal order. © 1990 BIT Foundations.