Bitonic sorter

EN Texto em inglês Ainda não há artigo no seu idioma: trecho em inglês.

Bitonic mergesort is a parallel algorithm for sorting. It is also used as a construction method for building a sorting network. The algorithm was devised by Ken Batcher. The resulting sorting networks consist of O ( n ( log ⁡ n ) 2 ) {\displaystyle {\mathcal {O}}(n(\log n)^{2})} comparators and have a delay of O ( ( log ⁡ n ) 2 ) {\displaystyle {\mathcal {O}}((\log n)^{2})} , where n {\displaystyle n} is the number of items to be sorted. This makes it a popular choice for sorting large numbers of elements on an architecture which itself contains a large number of parallel execution units running in lockstep, such as a typical GPU. A sorted sequence is a monotone sequence—that is, a sequence which is either non-decreasing or non-increasing. A sequence is bitonic when it consists of a non-decreasing sequence followed by a non-increasing sequence, i.e. when there exists an index m {\displaystyle m} for which x 0 ≤ ⋯ ≤ x m ≥ ⋯ ≥ x n − 1 . {\displaystyle x_{0}\leq \cdots \leq x_{m}\geq \cdots \geq x_{n-1}.} A bitonic sorter can only sort inputs that are bitonic. Bitonic sorters can be used to build a bitonic sort network that can sort arbitrary sequences by using the bitonic sorter with a sort-by-merge scheme, in which partial solutions are merged using bigger sorters. The following sections present the algorithm in its original formulation, which requires an input sequence whose length n {\displaystyle n} is a perfect power of two. We will therefore let k = log 2 ⁡ ( n ) {\displaystyle k=\log _{2}(n)} be the integer for which n = 2 k {\displaystyle n=2^{k}} , meaning that the bitonic sorters may be enumerated in order of increasing size by considering the successive values k = 1 , 2 ,...