Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 3,727 papers for “parallel sorting”

Parallel Multitonic Sorting Networks.

Tse-Yun Feng, Lee,Chung-chang · Defense Technical Information Center (DTIC) · 1976

This report is a study of the characteristics of multitonic sequences applied to parallel sorting networks. The main concern is the interconnections among the comparison levels of the sorting networks. A sorting network depends on various sorting algorithms and basic comparison element (BCE) implementation. A BCE is a device which can compare inputs and yields ordered outputs either in ascending order or in descending order. In order to facilitate analysis, the investigation is first confined to each BCE accepting two inputs only. With this restriction, sorting algorithms for parallel processing are described. Next, a new technique of graphic method is introduced, which helps the analysis of characteristics of multitonic sequences with respect to 2-sorters, and leads to the construction of perfect shuffle networks with '0' and '1' operations. Finally, the same technique of graphic method is also applied to construct perfect shuffle networks with BCE's that can accept three inputs.

Cited by 0

Towards optimal parallel radix sorting

Ramachandran Vaidyanathan, C. Hartmann, Pramod K. Varshney · 2002

The authors propose a radix sorting algorithm for n m-bit numbers (where m= Omega (log n) and polynomially upper bounded in n) that runs in O(t(n)log m) time, on any PRAM with mp(n)/logn logm O(logn)-bit processors; p(n) and t(n) are the number of processors and time needed for any deterministic algorithm to sort n logn-bit numbers stably (integer sorting) on the same type of PRAM as used by the radix sorting algorithm. The proposed algorithm has the same factor of inefficiency (if any) as that of the integer sorting algorithm used by it.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

Cited by 7

Parallel Computing for Sorting Algorithms

Baghdad Science Journal · Baghdad Science Journal · 2014

The expanding use of multi-processor supercomputers has made a significant impact on the speed and size of many problems. The adaptation of standard Message Passing Interface protocol (MPI) has enabled programmers to write portable and efficient codes across a wide variety of parallel architectures. Sorting is one of the most common operations performed by a computer. Because sorted data are easier to manipulate than randomly ordered data, many algorithms require sorted data. Sorting is of additional importance to parallel computing because of its close relation to the task of routing data among processes, which is an essential part of many parallel algorithms. In this paper, sequential sorting algorithms, the parallel implementation of many sorting methods in a variety of ways using MPICH.NT.1.2.3 library under C++ programming language and comparisons between the parallel and sequential implementations are presented. Then, these methods are used in the image processing field. It have been built a median filter based on these submitted algorithms. As the parallel platform is unavailable, the time is computed in terms of a number of computations steps and communications steps

Cited by 0Open access

Empirical Studies in Parallel Sorting

Golub, Evan · Digital Repository at the University of Maryland (University of Maryland College Park) · 1998

I examine different parallel algorithms for sorting in rounds. Most of these algorithms use a graph to indicate the comparisons to be made. The primary difference between the algorithms is how these graphs are chosen. One uses graphs that are shown to exist using non-constructive techniques, several yield constructions of the required graphs, and one uses a randomized algorithm. The constructive algorithms would traditionally be preferred even though the processor requirements are higher. It is shown that the non- constructive algorithms can actually be used by generating the needed graphs using random number generators skewed appropriately.

Cited by 0Open access

Dual Parallel Partition Sorting Algorithm

Apisit Rattanatranurak, C Hoare, R Sedgewick et al. · Proceedings of 2018 the 8th International Workshop on Computer Science and Engineering · 2018

Sorting is the important algorithm which is widely used and implemented in many applications. This paper presents an efficient parallel sorting algorithm called Dual Parallel Partition sorting (DPPSort). The DPPSort partitions the data recursively and then sorts in parallel. The partitioning phase divides the data into two parts in parallel. In sorting phase, the Standard Template Library Sorting function (STLSort) and GNU sorting function (qsort) are integrated in this work. This work is developed in C/C++ language and linked with OpenMP library. In our experiments, the 4-core Intel i7-3770 with Ubuntu Linux systems is implemented. Our work is faster than qsort and STLSort function up to 5.95 and 4.70, respectively.

Cited by 1Open access

Parallel Searching, Merging, and Sorting

Jesper Larsson Träff · 1996

This report contains fork implementations of parallel algorithms for searching and merging of ordered arrays, as well as elementary sorting algorithms, all part of the PAD library of basic PRAM Algorithms and Data structures. Among the implemented algorithms are the CREW merge algorithm of Hagerup and Rub running in O(log n + n=p) time, a merge sort and a deterministic Quicksort both running in O(log 2 n + n log n=p) time, and an algorithm for sorting small integers based on an idea of Cole and Vishkin running in O(log n + n=p) time, where n is the (total) length of the input and p the number of available processors. Quicksort and the small integer sort are able to exploit the multiprefix operations of the SB-PRAM, and therefore run in time O(log n+n log n=p) and O(n=p), respectively, on this machine. The merge and sort algorithms are work-optimal, and the implementations exhibit good relative and absolute speed-up, as indicated by a series of experiments performed using a simulator ...

Cited by 0

Constant-time parallel integer sorting

Torben Hagerup · 1991

Article Free Access Share on Constant-time parallel integer sorting Author: Torben Hagerup Max-Planck-Institut fu¨r Informatik, Saarbrucken, Germany Max-Planck-Institut fu¨r Informatik, Saarbrucken, GermanyView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 299–306https://doi.org/10.1145/103418.103452Online:03 January 1991Publication History 17citation341DownloadsMetricsTotal Citations17Total Downloads341Last 12 Months6Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Cited by 26Open access

AnEfficient Parallel Sorting Algorithm onOTISMeshofTrees

Prasanta K. Jana · 2009

corn Abstract: OTIS(Optical Transpose Interconnection 58to54.A parallel sorting forN dataelements on System) ispopular modelofoptoelectronic parallelOTIS-Mesh wasreported byRajasekaran andSahni (9) computers. Thisis a hybridinterconnection withatimecomplexity of8N+ o(N). Another sorting network using electronic and opticalalgorithm onthesamemodelwasproposed in(10) communication channels. Intherecent years, many with4N+O(N213 )time. parallel algorithms forvarious numericandnon- numericcomputations havebeendeveloped on these networks. Inthis paper, wepropose aparallelI t algorithm forsorting N (=n2) dataelements on an Interconnection System) (11), (12) hasgained OTISmodelofparallel computers, called OTIS- enormous popularity amongresearchers. OTISis Meshoftrees. Ouralgorithm isbasedonsparse basically a hybridinterconnection networkusing enumeration sortIllandshowntorunin4.5log N electronic andoptical channels. Theprocessors, in electronic moves+5OTISmoves, thesesystems, areorganized intogroups. Allthe processors within a groupare connected byusual

Cited by 0

More Efficient Parallel Integer Sorting

Yijie Han, Xin He · International Journal of Foundations of Computer Science · 2022

We present a more efficient CREW PRAM algorithm for integer sorting. This algorithm sorts [Formula: see text] integers in [Formula: see text] in [Formula: see text] time and [Formula: see text] operations. It also sorts [Formula: see text] integers in [Formula: see text] in [Formula: see text] time and [Formula: see text] operations. Previous best algorithm [15] on both cases has time complexity [Formula: see text] but operation complexity [Formula: see text].

Cited by 1

Parallel Computing for Sorting Algorithms

Zainab T. Baqer · Baghdad Science Journal · 2024

The expanding use of multi-processor supercomputers has made a significant impact on the speed and size of many problems. The adaptation of standard Message Passing Interface protocol (MPI) has enabled programmers to write portable and efficient codes across a wide variety of parallel architectures. Sorting is one of the most common operations performed by a computer. Because sorted data are easier to manipulate than randomly ordered data, many algorithms require sorted data. Sorting is of additional importance to parallel computing because of its close relation to the task of routing data among processes, which is an essential part of many parallel algorithms. In this paper, sequential sorting algorithms, the parallel implementation of many sorting methods in a variety of ways using MPICH.NT.1.2.3 library under C++ programming language and comparisons between the parallel and sequential implementations are presented. Then, these methods are used in the image processing field. It have been built a median filter based on these submitted algorithms. As the parallel platform is unavailable, the time is computed in terms of a number of computations steps and communications steps

Cited by 1Open access

A taxonomy of parallel sorting

Dina Bitton, David J. DeWitt, David K. Hsaio et al. · ACM Computing Surveys · 1984

We propose a taxonomy of parallel sorting that encompasses a broad range of array-and file-sorting algorithms. We analyze how research on parallel sorting has evolved, from the earliest sorting networks to shared memory algorithms and VLSI sorters.

Cited by 170Open access