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 |
Page view(s)
113
checked on Apr 2, 2025
Download(s)
44
checked on Apr 2, 2025
Google ScholarTM
Check
Items in Media are protected by copyright, with all rights reserved, unless otherwise indicated.