Adaptive Bitonic Sorting
File | Description | Size | Format | |
---|---|---|---|---|
Zachmann_Adaptive bitonic sorting_2013_accepted-version_PDF-A.pdf | 1.49 MB | Adobe PDF | View/Open |
Authors: | Zachmann, Gabriel ![]() |
Abstract: | 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. |
Keywords: | sorting algorithm; bitonic sorting | Issue Date: | 2011 | Publisher: | Springer | Journal/Edited collection: | Encyclopedia of Parallel Computing | Start page: | 146 | End page: | 157 | Type: | Artikel/Aufsatz | ISBN: | 978-0-387-09766-4 | Secondary publication: | yes | Document version: | Postprint | DOI: | 10.26092/elib/2364 | URN: | urn:nbn:de:gbv:46-elib70439 | Institution: | Universität Bremen | Faculty: | Fachbereich 03: Mathematik/Informatik (FB 03) |
Appears in Collections: | Forschungsdokumente |
Items in Media are protected by copyright, with all rights reserved, unless otherwise indicated.