Encyclopedia of Parallel Computing

Journal description

Journal Title

Encyclopedia of Parallel Computing

Now showing 1 - 1 of 1

Some of the metrics are blocked by your
consent settings
Adaptive Bitonic Sorting
(Springer, 2011)
Zachmann, Gabriel
Adaptive bitonic sorting is a sorting algorithm suitable for implementation on EREW parallel architectures. Similar to bitonic sorting, it is based on merging, which is recursively applied to obtain a sorted sequence. In contrast to bitonic sorting, it is data dependent. Adaptive bitonic merging can be performed in O(n/p) parallel time, p being the number of processors, and executes only O(n) operations in total. Consequently, adaptive bitonic sorting can be performed in O(n log n/p) time, which is optimal. So, one of its advantages is that it executes a factor of O(log n) less operations than bitonic sorting. Another advantage is that it can be implemented efficiently on modern GPUs.
journal article
124 116