Applying Sorting Networks to Synthesize Optimized Sorting Libraries

Michael Codish, Luís Cruz-Filipe, Markus Nebel, Peter Schneider-Kamp

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


This paper presents an application of the theory of sorting networks to facilitate the synthesis of optimized general-purpose sorting libraries. Standard sorting libraries are often based on combinations of the classic Quicksort algorithm with insertion sort applied as base case for small, fixed, numbers of inputs. Unrolling the code for the base case by ignoring loop conditions eliminates branching, resulting in code equivalent to a sorting network. This enables further program transformations based on sorting network optimizations, and eventually the synthesis of code from sorting networks. We show that, if considering the number of comparisons and swaps, the theory predicts no real advantage of this approach. However, significant speed-ups are obtained when taking advantage of instruction level parallelism and non-branching conditional assignment instructions, both of which are common in modern CPU architectures. We provide empirical evidence that using code synthesized from efficient sorting networks as the base case for Quicksort libraries results in significant real-world speed-ups.
Original languageEnglish
Title of host publicationLogic-Based Program Synthesis and Transformation : 25th International Symposium, LOPSTR 2015, Siena, Italy, July 13-15, 2015. Revised Selected Papers
EditorsMoreno Falaschi
Publication dateDec 2015
ISBN (Print)978-3-319-27435-5
ISBN (Electronic)978-3-319-27436-2
Publication statusPublished - Dec 2015
Event25th International Symposium on Logic-based Program Synthesis and Transformation - Siena, Italy
Duration: 13. Jul 201515. Jul 2015


Conference25th International Symposium on Logic-based Program Synthesis and Transformation
SeriesLecture Notes in Computer Science


Dive into the research topics of 'Applying Sorting Networks to Synthesize Optimized Sorting Libraries'. Together they form a unique fingerprint.

Cite this