tag

#sorting-network

8 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

Bitonic Merge Network

Bitonic Merge Network The bitonic merge network is the core component of bitonic sorting. It takes a bitonic sequence and transforms it into a fully sorted sequence using a fixed pattern of compare and exchange operations. A sequence is bitonic when it consists of an increasing part followed by a decreasing part, or can be rotated into that form. Problem Given a bitonic sequence of length $n$, produce a sorted...
algorithms sorting sorting-network bitonic-merge
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

Bitonic Sorting Network

Bitonic Sorting Network A bitonic sorting network is a fixed sequence of compare and exchange operations that sorts a fixed number of elements. It is based on the idea of repeatedly building bitonic sequences and merging them. A bitonic sequence increases and then decreases, or can be rotated into that shape. The network first creates bitonic sequences of small size, then merges them into larger sorted sequences until the full...
algorithms sorting sorting-network bitonic-sort
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Pairwise Sorting Network

Pairwise Sorting Network Pairwise sorting network is a comparison sorting algorithm defined as a fixed network of compare and swap operations. It performs sorting through a sequence of pairwise comparisons arranged in stages. Unlike adaptive algorithms, its structure does not depend on input values. This makes it suitable for parallel execution and hardware implementation. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1]...
algorithms sorting sorting-network pairwise
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Odd Even Merge Sort

Odd Even Merge Sort Odd even merge sort is a comparison sorting algorithm designed as a sorting network. It uses a fixed pattern of compare and swap operations, independent of the input values. It is closely related to bitonic sort but uses a different merging strategy. It is especially useful in parallel hardware and SIMD execution environments. Problem Given an array $A$ of length $n$, reorder it such that: $$...
algorithms sorting sorting-network odd-even-merge
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

Odd Even Sorting Network

Odd Even Sorting Network The odd even sorting network is a fixed comparator network derived from odd even transposition sort. It repeatedly applies two phases: compare adjacent pairs starting at even indices, then compare adjacent pairs starting at odd indices. The schedule is fixed and independent of input values. All comparisons within one phase are independent and can run in parallel. Problem Given $n$ elements, sort them in nondecreasing order...
algorithms sorting sorting-network odd-even-sort
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Batcher Merge Sort

Batcher Merge Sort Batcher merge sort is a sorting network algorithm. It sorts two halves recursively, then merges them using Batcher's odd even merge network. Its comparison pattern is fixed before execution. The same compare and swap operations run regardless of the input values. This makes it useful for parallel machines, SIMD code, GPUs, and hardware circuits. Problem Given an array $A$ of length $n$, reorder it such that: $$...
algorithms sorting sorting-network batcher-merge-sort
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

SIMD Sorting Network

SIMD Sorting Network A SIMD sorting network sorts a fixed number of elements using a predetermined sequence of compare and exchange operations. Each stage can be mapped to vector instructions such as lane permutation, vector minimum, vector maximum, and blend. Unlike comparison sorts with branches, the schedule does not depend on input values. This makes the method useful for short arrays, database kernels, vectorized partitioning, and base cases inside larger...
algorithms sorting simd sorting-network
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Bitonic Sort

Bitonic Sort Bitonic sort is a comparison sorting algorithm based on bitonic sequences. It is important because its compare and swap pattern is fixed, which makes it suitable for parallel hardware and sorting networks. A bitonic sequence first increases and then decreases, or can be rotated into that form. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots \le A[n-1] $$...
algorithms sorting bitonic-sort sorting-network