17-03-2014, 06:23 PM
Abstract
This paper studies the bitonic merge sort algorithm
which is difficult to get the prospective sorted result for
some odd sequence. We develop a new parallel sorting
algorithm, increasing CCI(compare and conditionally
interchange) operations, derived from the odd merge sort
algorithm. The proposed algorithm is based on a divideand-
conquer strategy. First of all, the sequence to be
sorted is decomposed in several groups that are sorted in
parallel. After that, all groups are merged into a final,
sorted sequence. Therefore, any odd bitonic sequence can
be correctly sorted with the mended algorithm,
Furthermore, The paper analyzes the computational
complexity of the new algorithm and compares it with
that of other well-known parallel sorting algorithms. It
does not increase memory consumption, and keep the
same complexity. Analytic results are compared with
those of the sequential algorithm and parallel
implementations of other sorting algorithms, obtaining
that our proposal outperforms the other solutions.
1. Introduction
The subject of parallel sorting networks has been
studied extensively in the past not only because parallel
sorting is an interesting topic to explore in its own right
but also because its important applications. Some of these
applications are sketched below: as communication[1], a
multi-access memory, a multi-access content memory and
as a multiprocessor[2], as a switching network with
buffering[3],of course, the networks also may be used just
for sorting and merging.
In 1968, Batcher[4,5] puts forward two famous sorting
Algorithms: Parity sorting algorithm and Bitonic Sorting
Algorithm. Recent work by Thompson[6], Ja’Ja’[7], Nakatani[
8], Lee Guan[9] , Preparata[10] and Langston[11] has been
devoted to parallel merging sort. The basic theme of
these papers has been to speed up sorting. The fast sorting
capability of these networks allows their use in solving
other problems where large sets of data must be
manipulated.
This paper describes networks that have a fast sorting
or ordering capability (sorting networks or sorting
memories). A sorting network can be used as a multiple
input, multiple-output switching network. Besides the fast
sorting, the algorithm proposed in this paper can correctly
sort for any odd bitonic sequence.
This paper studies the bitonic merge sort algorithm
which is difficult to get the prospective sorted result for
some odd sequence. We develop a new parallel sorting
algorithm, increasing CCI(compare and conditionally
interchange) operations, derived from the odd merge sort
algorithm. The proposed algorithm is based on a divideand-
conquer strategy. First of all, the sequence to be
sorted is decomposed in several groups that are sorted in
parallel. After that, all groups are merged into a final,
sorted sequence. Therefore, any odd bitonic sequence can
be correctly sorted with the mended algorithm,
Furthermore, The paper analyzes the computational
complexity of the new algorithm and compares it with
that of other well-known parallel sorting algorithms. It
does not increase memory consumption, and keep the
same complexity. Analytic results are compared with
those of the sequential algorithm and parallel
implementations of other sorting algorithms, obtaining
that our proposal outperforms the other solutions.
1. Introduction
The subject of parallel sorting networks has been
studied extensively in the past not only because parallel
sorting is an interesting topic to explore in its own right
but also because its important applications. Some of these
applications are sketched below: as communication[1], a
multi-access memory, a multi-access content memory and
as a multiprocessor[2], as a switching network with
buffering[3],of course, the networks also may be used just
for sorting and merging.
In 1968, Batcher[4,5] puts forward two famous sorting
Algorithms: Parity sorting algorithm and Bitonic Sorting
Algorithm. Recent work by Thompson[6], Ja’Ja’[7], Nakatani[
8], Lee Guan[9] , Preparata[10] and Langston[11] has been
devoted to parallel merging sort. The basic theme of
these papers has been to speed up sorting. The fast sorting
capability of these networks allows their use in solving
other problems where large sets of data must be
manipulated.
This paper describes networks that have a fast sorting
or ordering capability (sorting networks or sorting
memories). A sorting network can be used as a multiple
input, multiple-output switching network. Besides the fast
sorting, the algorithm proposed in this paper can correctly
sort for any odd bitonic sequence.