Optimizing sorting algorithms by using sorting networks
Sorting is one of the most fundamental problems in computer science since it is needed as a subroutine in many applications. This paper brings together two major branches of research on sorting. On the one hand there is the ongoing quest for the best sorting software on mainstream microprocessors -- mostly for sorting rather large inputs. On the other hand, there is a more specialized branch of research on sorting networks. These consist of elementary circuits (comparators) that take two input elements and output them in sorted order. Considerable research has been done on finding sorting networks with minimal size (number of comparators) or minimal depth (longest path) for small inputs (up to 20 elements). The connection between these two subjects is that most successful sorting algorithms break down the problem of sorting large inputs into many sorting problems for small inputs. Although these base cases constitute only an asymptotically vanishing fraction of the overall work, they constitute a surprisingly large fraction of the total work in practice. Equally surprisingly, the state of the art is to use a simple algorithm with quadratic complexity for the base cases (insertion sort). Using sorting networks for the base case is attractive since they need less comparisons than insertion sort and because no conditional branches are needed (in contrast to an alternative approach of using complex if-then-else nests which are very expensive on modern architectures that rely on high quality branch predictions). It turns out that additional algorithm engineering is needed to make this idea work well:{\parindent=0.7cm\begin{itemize}\item[--] Make sure that actually no conditional branches are made. \item[--] Exploit instruction level parallelism. \item[--] For inputs that do not fit into the register file, use networks that do not need too many memory accesses. \end{itemize}} Overall, a quicksort implementation using optimized sorting networks as base case can be up to 20\% faster than one using insertion sort.
- Sorting with networks of data structures
- Optimal sorting networks
- Applying sorting networks to synthesize optimized sorting libraries
- Slowing down sorting networks to obtain faster sorting algorithms
- On optimal parallelization of sorting networks
- scientific article; zbMATH DE number 4031004
- Improved sorting networks with O(log N) depth
- Optimal-depth sorting networks
- New Bounds on Optimal Sorting Networks
- A computer-assisted optimal depth lower bound for nine-input sorting networks
- A Simple Sorting Algorithm
- A Sorting Problem
- Applying sorting networks to synthesize optimized sorting libraries
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- scientific article; zbMATH DE number 1330906 (Why is no real title available?)
- scientific article; zbMATH DE number 2155520 (Why is no real title available?)
- scientific article; zbMATH DE number 815575 (Why is no real title available?)
- New Bounds on Optimal Sorting Networks
- Optimal sorting networks
- Quicksort
- Sorting networks: the end game
- Sorting nine inputs requires twenty-five comparisons
- The analysis of Quicksort programs
- Sorting-based selection algorithms for hypercubic networks
- Increasing the Efficiency of Existing Sorting Algorithms by Using Randomized Wrappers
- Using symmetry and evolutionary search to minimize sorting networks
- Applying sorting networks to synthesize optimized sorting libraries
- Improved sorting networks with O(log N) depth
- An 11-step sorting network for 18 elements
- Accelerating certain outputs of merging and sorting networks
- Improved layout of the odd-even sorting network
This page was built for publication: Optimizing sorting algorithms by using sorting networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2628305)
