Search

В данной статье рассказывается о возможном варианте оптимизации алгоритма сортировки Timsort.

Sorting is considered as one of the most well-known problems in the computer world. It is a common process among several application areas, such as real time decision support systems and intelligent transport applications. In this paper, we propose a software implementation for different sorting algorithms, such as InsertionSort, QuickSort, HeapSort, ShellSort, MergeSort and TimSort on the Zynq Zedboard platform. In addition, the performance of the different algorithms are compared in terms of averages and standard-deviation of computational time, energy consumption and stability. As demonstrated by the experimental results, the ShellSort is 42.1% faster and can even reach 72% when running on the ARM Cortex A9 processor mainly if the number of elements (n) to be sorted is greater than 64. Otherwise, TimSort is the best algorithm. Also, ShellSort is the best algorithm in terms of standard-deviation of computational times and energy consumption.

One of the main topics in computer science is how to perform data classification without requiring plenty of resources and time. The sorting algorithms Quicksort, Mergesort, Timsort, Heapsort, Bubblesort, Insertion Sort, Selection Sort, Tree Sort, Shell Sort, Radix Sort, Counting Sort, are the most recognized and used. The existence of different sorting algorithm options led us to ask: What is the algorithm that us better execution times? Under this context, it was necessary to understand the various sorting algorithms in C and Python programming language to evaluate them and determine which one has the shortest execution time. We implement algorithms that help create four types of integer arrays (random, almost ordered, inverted, and few unique). We implement eleven classification algorithms to record each execution time, using different elements and iterations to verify the accuracy. We carry out the research using the integrated development environments Dev-C++ 5.11 and Sublime Text 3. The products allow us to identify different situations in which each algorithm shows better execution times.

TimSort is the main sorting algorithm provided by the Java standard library and many other programming frameworks. Our original goal was functional verification of TimSort with mechanical proofs. However, during our verification attempt we discovered a bug which causes the implementation to crash by an uncaught exception. In this paper, we identify conditions under which the bug occurs, and from this we derive a bug-free version that does not compromise performance. We formally specify the new version and verify termination and the absence of exceptions including the bug. This verification is carried out mechanically with KeY, a state-of-the-art interactive verification tool for Java. We provide a detailed description and analysis of the proofs. The complexity of the proofs required extensions and new capabilities in KeY, including symbolic state merging.

Parallel sorting algorithms are widely studied nowadays. After the introduction of parallel processors such as graphics processing unit (GPU) and easy to use parallel programming languages such as CUDA and OpenCL, literature on parallel sorting algorithms has become vast and richer with new ideas and techniques applied to solve the famous problem of sorting. This paper presents a survey of GPU based sorting algorithms. Four sorting algorithms have been selected for this survey: Radix sort, Merge sort, Sample sort and Quick sort. Methods used in those algorithms are described in brief. The performance of these algorithms as claimed by their authors is also presented. A comparative analysis based on the literature is depicted.

Timsort je jedan od najkorištenijih algoritama danas te ga razni programski jezici koriste kao standardni algoritam za sortiranje. U uvodnom dijelu dajemo kratki opis problema sortiranja i uvodimo određene pojmove vezane za sortiranje koji nam koriste da bismo lakše raspravljali o svojstvima Timsorta. Zatim dokazujemo donju granicu za složenost uspoređujućih algoritama i prikazujemo povijest algoritama za sortiranje, te neke od njih detaljnije opisujemo. Glavni dio rada se sastoji od ilustriranja načina rada i dokaza složenosti Timsorta. Prvo opisujemo kako radi algoritam, zatim na izvornom kodu detaljno objašnjavamo sve funkcije i svaki korak algoritma. Na kraju dajemo dokaz \(\mathcal{O}(n\log n)\) složenosti Timsorta, što je najbolja moguća složenost za uspoređujuće algoritme. Timsort is one of the most widely used algorithms today. For many programming languages it is the standard sorting algorithm used. In the introductory part a short description of the problem of sorting is presented and we introduce certain definitions related to sorting that help us discuss some of Timsort’s properties. We then provide a proof of the lower bound for the complexity of comparison sort algorithms and present the history of sorting algorithms, some of which we explain in further detail. The main part of the thesis is comprised of illustrating the sorting process of Timsort and a proof of its complexity. First, we describe how the algorithm works. Then, using the source code, we explain in further detail all the functions and every step of the algorithm. Lastly, we provide a proof for Timsort’s \(\mathcal{O}(n\log n)\) complexity, which is the best possible for comparison sort algorithms.

Sorting algorithms are the class of algorithms that result in the ordered arrangement of a list of given elements. The arrangement can be in ascending or descending order based on the requirement given. Time complexity, space complexity and optimality are used to assess the algorithms. In this paper, a new sorting algorithm called Matrix sort is introduced. This algorithm aims to sort the elements of a matrix without disturbing the matrix structure. It has a time complexity of O(n p nlog p n) and hence takes lesser time than existing O(n 2 ) algorithms. A pseudocode for the algorithm is provided and the best, average and worst case time complexities are derived.

The work purpose is not only to implement a computer interactive learning system methods of sort, visualize sorting methods, but to demonstrate the impact of appropriately chosen data structures in the computational process. After all, according to the well-known formula N. Wirth: "Algorithms + data Structures = Programs". Sorting is a good method of showing how the goal can be achieved by different methods (algorithms), each with their advantages and disadvantages, assessed from the point of view of the cash inputs and requirements. To achieve the didactic purposes we use the Delphi environment to ensure the efficient work of the programmers, with the involvement of the full potential of Windows. Multi-window capabilities of the medium, ease of coding programs make possible implementation of an interactive learning system sorting numbers. Analyze performance indicators of the method of sorting is the number of comparisons and permutations. They are the basic operations performed on numeric vectors. You should determine an effective and relevant method of sorting according to these two indicators. Really, the probability of operating with a large dataset – more than the small, should, therefore identify the most effective method for computer resources (speed sorting and memory use). For each method, the user receives the necessary information on the sorting method, the system then sorts the sequence of steps interactively with visualization. A comparative analysis of methods of sorting, the results of the analysis to identify an effective method of sorting.

TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint. In fact, there are two slightly different versions of TimSort that are currently implemented in Python and in Java respectively. We propose a pedagogical and insightful proof that the Python version runs in $\mathcal{O}(n\log n)$. The approach we use in the analysis also applies to the Java version, although not without very involved technical details. As a byproduct of our study, we uncover a bug in the Java implementation that can cause the sorting method to fail during the execution. We also give a proof that Python's TimSort running time is in $\mathcal{O}(n + n\log \rho)$, where $\rho$ is the number of runs (i.e. maximal monotonic sequences), which is quite a natural parameter here and part of the explanation for the good behavior of TimSort on partially sorted inputs.

Sorting a list of items is one basic task in many applications used on the computer. The term describes the arrangement of a set of items in a certain order to make analysis and processing very easy. Numerous sorting algorithms exist however its efficiency and memory space consumption become a major issue when it has to be implemented.Essentially, programmers select sort algorithms that perform well even as the size of the input data increases. In this study, a new algorithm, Magnetic Bubble Sort Algorithm (MBS) is proposed. The MBS is an enhancement of the bubble sort algorithm which offers a far better performance in the case where redundancies occur in the list. The run time of the MBS depends on the number of distinct values that are found in the list to be sorted.The improved bubble sort algorithm is very simple to analyse, considering the fact that the time complexity of the algorithm depends on two main factors that is the size of list (n) and number of distinct values in the list.

Two-way merge sort algorithm has a good time efficiency which has been used widely. The sort algorithm can be improved on speed and efficient based on its own potential parallelism via the parallel processing capacity of multi-core processor and the convenient programming interface of OpenMP. The time complexity is improved to O(nlog2n/TNUM) and inversely proportional to the number of parallel threads. The experiment results show that the improved two-way merge sort algorithm become much more efficient compared to the traditional one.

Modern architectures make possible development in new algorithms for large data sets and distributed computing. The newly proposed versions can benefit both from faster computing on the multi core architectures, and intelligent programming techniques that use efficient procedures available in the latest programming studios. Frequently used algorithms to sort arrays of data in NoSQL databases is merge sort, where as NoSQL we understand any database without typical SQL programming interpreter. The author describes how to use the parallelization of the sorting processes for the modified method of sorting by merging for large data sets. The subject of this research is the claim that the parallelization of the sorting method is faster and beneficial for multi-core systems. Presented results show how the number of processors influences the sorting performance. The results are presented in theoretical assumptions and confirmed in practical benchmark tests. The method is compared to other sorting methods like quick sort, heap sort, and merge sort to show potential efficiency.

International audience; Sorting algorithms are one of the most commonly used in computer science. They can be seen as a pillar for some applications such as decision support systems, path planning, etc. However, sorting large number of elements needs high computation rate. Consequently, accelerating sorting algorithms using hardware implementation is an interesting solution to speed up computations. The purpose of this paper is to develop a hardware accelerated version of TimSort and MergeSort algorithms from high level descriptions. The algorithms are implemented using Zynq-7000 xilinx platform as part of real time decision support for avionic applications. As experimental results, we compare the performance of two algorithms in terms of execution time and resource utilization. We showed that TimSort ranges from 1.07x to 1.16x faster than MergeSort when optimized hardware is used.

The relevance of this topic is due to the constant increase of the volume of the sorted data at the present time, and the demand to increase speed of information processing. The aim of this work is a modification of the known sorting algorithms for their effective use on the CUDA platform, i.e. it is necessary to develop a program parallel sorting of data to compare its performance with the sequential version and systematize the results. Thus, the obtained results show that the use of the graphics accelerator can significantly increase the speed of applications that use the algorithms sort the data. With the growth of the COP-operated arrays and the size of the used blocks of work time, multi-threaded application on a GPU is reduced several tens of times compared to the sequential implementation on the CPU, and with the increase in the number of blocks of winning increases.

Choosing the right method to sort numbers has a huge effect on how quickly a computer can process a task. The most used sorting algorithms today have been discovered years ago, and to this day, they have been the best for the job as there was no other competitive algorithm. Through this paper, we make an analysis and comparison between the state of the art algorithms in sorting and based on their analogy of functionality, we propose a new modified sorting algorithm. We then present a brief description of the new modified algorithm, conduct comparisons with the state of the art, and finally we give conclusions about the performance of the proposed algorithm versus the most popular sorting algorithms. Moreover, we highlight the benefits of using this algorithm in different fields by various business companies or software developers, in cases when they need faster and easier sorting for their data management.

Non-dominated sorting is a technique often used in evolutionary algorithms to determine the quality of solutions in a population. The most common algorithm is the Fast Non-dominated Sort (FNS). This algorithm, however, has the drawback that its performance deteriorates when the population size grows. The same drawback applies also to other non-dominating sorting algorithms such as the Efficient Non-dominated Sort with Binary Strategy (ENS-BS). An algorithm suggested to overcome this drawback is the Divide-and-Conquer Non-dominated Sort (DCNS) which works well on a limited number of objectives but deteriorates when the number of objectives grows. This article presents a new, more efficient algorithm called the Efficient Non-dominated Sort with Non-Dominated Tree (ENS-NDT). ENS-NDT is an extension of the ENS-BS algorithm and uses a novel Non-Dominated Tree (NDTree) to speed up the non-dominated sorting. ENS-NDT is able to handle large population sizes and a large number of objectives more efficiently than existing algorithms for non-dominated sorting. In the article, it is shown that with ENS-NDT the runtime of multi-objective optimization algorithms such as the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) can be substantially reduced.

The modern CPU's design, which is composed of hierarchical memory and SIMD/vectorization capability, governs the potential for algorithms to be transformed into efficient implementations. The release of the AVX-512 changed things radically, and motivated us to search for an efficient sorting algorithm that can take advantage of it. In this paper, we describe the best strategy we have found, which is a novel two parts hybrid sort, based on the well-known Quicksort algorithm. The central partitioning operation is performed by a new algorithm, and small partitions/arrays are sorted using a branch-free Bitonic-based sort. This study is also an illustration of how classical algorithms can be adapted and enhanced by the AVX-512 extension. We evaluate the performance of our approach on a modern Intel Xeon Skylake and assess the different layers of our implementation by sorting/partitioning integers, double floating-point numbers, and key/value pairs of integers. Our results demonstrate that our approach is faster than two libraries of reference: the GNU \emph{C++} sort algorithm by a speedup factor of 4, and the Intel IPP library by a speedup factor of 1.4., Comment: 8 pages, research paper

Sorting is a fundamental functionality in libraries, for which efficiency is crucial. Correctness of the highly optimised implementations is often taken for granted. De Gouw et al. have shown that this certainty is deceptive by revealing a bug in the Java Development Kit (JDK) implementation of TimSort.

The paper is dedicated to fast FPGA-based hardware accelerators that implement sorting networks. The primary emphasis is on the uniformity of core components, feasible combinations of parallel, pipelined and sequential operations, and the regularity of the circuits and interconnections. The paper shows theoretically, and based on numerous experiments, that many existing solutions that are commonly considered to be very efficient have worthy competitors that are better for many practical problems. We compared the even-odd merge and bitonic merge sorting networks (which are among the fastest known) with the even-odd transition network, which is often characterized as significantly slower and more resource consuming. We found that the latter is the most regular network that can be implemented very efficiently in FPGA, so we are proposing new, easily scalable hardware solutions and processing techniques based on this. Finally, the paper provides four main contributions and suggests: (1) a regular hardware implementation of resource and time effective architectures based on the even-odd transition network; (2) a pipelined implementation of even-odd transition networks; (3) a pre-processing technique that enables sorting to be further accelerated; (4) combinations of this technique with a merge sort, an address-based sort, a quicksort, and a radix sort.

The parallel algorithm of merge sort is proposed. The improvements of merge sort are analyzed in this paper. OpenMP is applied in the proposed algorithm for implementation. The results of complexity and execution time of the proposed algorithm indicate that the parallel algorithm approach the optimal case.

Sorting has been a topic of immense research value since the inception of computer science. Hybrid computing on multicore architectures involves computing simultaneously on a tightly coupled heterogeneous collection of devices. In this work, we consider a multicore CPU along with a manycore GPU as our experimental hybrid platform. In this work, we present a hybrid comparison based sorting algorithm which utilizes a many-core GPU and a multi-core CPU to perform sorting. The algorithm is broadly based on splitting the input list according to a large number of splitters followed by creating independent sublists. Sorting the independent sublists results in sorting the entire original list. On a CPU + GPU platform consisting of an Intel i7-980X and an NVidia GTX 580, our algorithm achieves a 20% gain over the current best known comparison sort result that was published by (Davidson et al., 2012). On the above experimental platform, our results are better by 40% on average over a similar GPU-alone algorithm proposed by (Leischner et al., 2010). We also extend our sorting algorithm for fixed length keys to variable length keys. We use a look-ahead based approach to sort strings and obtain around a 24% benefit compared to the current best known solution. Our results also show that our algorithm and its implementation scale with the size of the input. We also show that such performance gains can be obtained on other hybrid CPU + GPU platforms.

Sorting is one of the fundamental operations of Computer Science. Many problems, such as plasma real-time diagnostic, image re-ranking, and suffix array construction, require that we sort several arrays in the form of matrix lines or array segments. We define this type of task as segmented sorting. Considering the importance of this problem, the main goal of this study is to provide insight into different techniques for solving it, while also answering the question "What is the best performing strategy?" for different combinations of array lengths and segment sizes. In order to perform segmented sorting, we can either call a sorting procedure for each of the array segments or use an implementation specialized in this operation. As an alternative, we explore an approach named fix sort, which adjusts the array to allow off-the-shelf general sorting algorithms to perform segmented sorting. We implemented and compared different methods to sort multiple segments in a shared memory environment using CUDA. Throughout our experiments, we noticed a great variation in performance when using the MGPU and CUB libraries, the bitonic sort from CUDA samples, the fix sort-based strategies, and a radix sort procedure called for each segment. The tests showed that using fix sort can be favorable in some cases, and enabled us to create a guideline for efficient implementation of segmented sorting routines based on the parameters of array lengths and number of segments.

Sorting is a classic problem that has been studied for decades. From the beginning of computing, many Sorting algorithms have been investigated. Bubble sort is a very common and powerful sorting technique used in different applications. For high speed data processing, we need faster and efficient environment for any sorting algorithm. In this purpose, FPGA based hardware accelerators can show better performance for high speed data processing than the general purpose processors. In this paper, the sequential and parallel bubble sort algorithm is implemented using FPGA. We show that parallel implementation of Bubble sort algorithm is almost 10 times faster than that of sequential implementation for 20 different data inputs. However, this implementation is faster for more data inputs.

This article considers the methods of sorting, i.e. placing the array of numbers, which are used in computer techniques today, according to the rule. Sorting is one of the most common principles of programming systems, while their application for various applied problems requires choosing an optimal sorting algorithm from a set of existing ones. The objective of the article is to analyze temporal characteristics of the selection process aimed at choosing the algorithm, which is the most suitable for a certain goal realization. Existing methods of sorting can be grouped into: sorting by insertion, sorting by selection, sorting by exchange. Existing methods are analyzed in terms of quantity indexes of exchanges, integrations and comparisons that define each algorithm at most. As a result, the total operating speed of each method was estimated; the advantages and disadvantages of each method were singled out. The results of analysis of well known sorting methods allow choosing the best method for software and hardware implementation from this point of view. The principal possibility of new solutions in the field of hardware implementation was shown in order to increase the level of parallelism and accelerate the sorting process, whereby the sorting method by exchange should be prerogative. After checking the known sorting methods for operating speed with the use of the constant volume array, the operation time of sorting programs was defined on the basis of different sorting methods. Yet, the sorting method of Shell and quick sort method have shown best results.

Parallel sorting is an essential algorithm in large-scale data analytics using distributed memory systems. As the number of processes increases, existing parallel sorting algorithms could become inefficient because of the unbalanced workload. A common cause of load imbalance is the skewness of data, which is common in application data sets from physics, biology, earth and planetary sciences. In this work, we introduce a new scalable dynamic skew-aware parallel sorting algorithm, named SDS-Sort. It uses a skew-aware partition method to guarantee a tighter upper bound on the workload of each process. To improve load balance among parallel processes, existing algorithms usually add extra variables to the sorting key, which increase the time needed to complete the sorting operation. SDS-Sort allows a user to select any sorting key without sacrificing performance. SDS-Sort also provides optimizations, including adaptive local merging, overlapping of data exchange and data processing, and dynamic selection of data processing algorithms for different hardware configurations and for partially ordered data. SDS-Sort uses local-sampling based partitioning to further reduce its overhead. We tested SDS-Sort extensively on Edison, a Cray XC30 supercomputer. Timing measurements show that SDS-Sort can scale to 130K CPU cores and deliver a sorting throughput of 117TB/min. In tests with real application data from large science projects, SDS-Sort outperforms HykSort, a state-of-art parallel sorting algorithm, by 3.4X.

Objective: Sorting is considered a very important application in many areas of computer science. Nowadays parallelization of sorting algorithms using GPU computing, on CUDA hardware is increasing rapidly. The objective behind using GPU computing is that the users can get, the more speedup of the algorithms. Methods: In this paper, we have focused on count sort. It is very efficient sort with time complexity O(n). The problem with count sort is that, it is not recommended for larger sets of data because it depends on the range of key elements.In this paper this drawback has been taken for the research concern and we parallelized the count sort using GPU computing with CUDA. Findings: We have measured the speedup achieved by the parallel count sort over sequential count sort. The sorting benchmark has been used to test and measure the performance of both the versions of count sort (parallel and sequential). The sorting benchmark has six types of test cases which are uniform, bucket, Gaussian, sorted, staggered and zero.In this paper, our finding is that we have tested the parallel and sequential count sort on a larger sets of data which vary from N=1000 to N=10000000. Improvement: After testing, we have achieved 66 times more efficient results of the parallel count sort in the case of execution time using Gaussian test case. We found that the parallel count sort performs, the better experimental results over sequential in all the test cases.

Accelerating database applications using FPGAs has recently been an area of growing interest in both academia and industry. Equi-join is one of the key database operations whose performance highly depends on sorting, which exhibitshigh memory usage on FPGA. A fully pipelined N-key mergesorter consists of log N sorting stages using O(N) memorytotally. For large data sets, external memory has to be employedto perform data buffering between the sorting stages. Thisintroduces pipeline stalls as well as several iterations betweenFPGA and external memory, causing significant performancedegradation. In this paper, we speed-up equi-join using a hybridCPU-FPGA heterogeneous platform. To alleviate the performanceimpact of limited memory, we propose a merge sort based hybriddesign where the first few sorting stages in the merge sort tree are replaced with "folded" bitonic sorting networks. These "folded" bitonic sorting networks operate in parallel on the FPGA. Thepartial results are then merged on the CPU to produce the finalsorted result. Based on this hybrid sorting design, we develop twostreaming join algorithms by optimizing the classic CPU-basednested-loop join and sort-merge join algorithms. On a rangeof data set sizes, our design achieves throughput improvementof 3.1x and 1.9x compared with software-only and FPGA onlyimplementations, respectively. Our design sustains 21.6% of thepeak bandwidth, which is 3.9x utilization obtained by the state-of-the-art FPGA equi-join implementation.

Sorting has tremendous usage in the applications that handle massive amount of data. Existing techniques accelerate sorting using multiprocessors or GPGPUs where a data set is partitioned into disjunctive subsets to allow multiple sorting threads working in parallel. Hardware sorters implemented in FPGAs have the potential of providing high-speed and low-energy solutions but the partition algorithms used in software systems are so data dependent that they cannot be easily adopted. The speed of most current sequential sorters still hangs around 1 number/cycle. Recently a new hardware merge sorter broke this speed limit by merging a large number of sorted sequences at a speed proportional to the number of sequences. This paper significantly improves its area and speed scalability by allowing stalls and variable sorting rate. A 32-port parallel merge-tree that merges 32 sequences is implemented in a Virtex-7 FPGA. It merges sequences at an average rate of 31.05 number/cycle and reduces the total sorting time by 160 times compared with traditional sequential sorters.

There are many sorting techniques which were developed over the hundreds of years and also optimized to reduce the complexity for worst and average cases. This paper presents a technique, that can be used to optimize the sorting algorithms, named CutShort. The name ‘CutShort’ signifies cutting of original array into shorter pieces. In this technique, the input array is divided into several subarray of shorter lengths based on bit-count, somewhat similar to the Bucket sort concept. Here each sub-arrays contains those elements which can be represented by same number of bits. We have tested this proposed technique on random samples of large input array and the results are very satisfactory. This technique reduces the complexity of worst and average case by a significant factor depending on the number of sub-arrays formed. This method can be used as a preprocessing technique and can be more beneficial if implemented in the processor as a subroutine. It can be used to optimize the runtime of various sorting algorithms.

Sorting is an important algorithmic task used in many applications. Two main aspects of sorting algorithms which have been studied extensively are complexity and correctness. [Foley and Hoare, 1971] published the first formal correctness proof of a sorting algorithm (Quicksort). While this is a handwritten proof, the development and application of (semi)-automated theorem provers has since taken a huge flight. The major sorting algorithms Insertion sort, Heapsort and Quicksort were proven correct by Filliâtre and Magaud [1999] using the proof assistant Coq. Recently, Sternagel [2013] formalized a proof of Mergesort within the interactive theorem prover Isabelle/HOL.

In this paper, we proposed a new efficient sorting algorithm based on insertion sort concept. The proposed algorithm called Bidirectional Conditional Insertion Sort (BCIS). It is in-place sorting algorithm and it has remarkably efficient average case time complexity when compared with classical insertion sort (IS). By comparing our new proposed algorithm with the Quicksort algorithm, BCIS indicated faster average case time for relatively small size arrays up to 1500 elements. Furthermore, BCIS was observed to be faster than Quicksort within high rate of duplicated elements even for large size array., Comment: references not appeared cause arxiv system does not uploaded .bib files

The challenge of direct parameterized suffix sorting (p-suffix sorting) for a parameterized string (p-string), say T of length-n, is the dynamic nature of the n parameterized suffixes (p-suffixes) of T. In this work, we propose transformative approaches to direct p-suffix sorting by generating and sorting lexicographically numeric fingerprints and arithmetic codes that correspond to individual p-suffixes. Our algorithm to p-suffix sort via fingerprints is the first theoretical linear time algorithm for p-suffix sorting for non-binary parameter alphabets, which assumes that, in practice, all codes are within the range of an integral data type. We eliminate the key problems of fingerprints by introducing an algorithm that exploits the ordering of arithmetic codes to sort p-suffixes in linear time on average. The arithmetic coding approach is further extended to handle p-strings in the worst case. This algorithm is the first direct p-suffix sorting approach in theory to execute in o(n2) time in the worst case, which improves on the best known theoretical result on this problem that sorts p-suffixes based on p-suffix classifications in O(n2) time. We show that, based on the algorithmic parameters and the input data, our algorithm does indeed execute in linear time in various cases, which is confirmed with experimental results.

Sorting appears the most attention among all computational tasks over the past years because sorted data is at the heart of many computations. 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. Many parallel sorting algorithms have been investigated for a variety of parallel computer architectures. In this paper, three parallel sorting algorithms have been implemented and compared in terms of their overall execution time. The algorithms implemented are the odd-even transposition sort, parallel merge sort and parallel shell sort. Cluster of Workstations or Windows Compute Cluster has been used to compare the algorithms implemented. The C# programming language is used to develop the sorting algorithms. The MPI library has been selected to establish the communication and synchronization between processors. The time complexity for each parallel sorting algorithm will also be mentioned and analyzed.

Many database applications require sorting a table (or relation) over multiple sort orders. Some examples include creation of multiple indices on a relation, generation of multiple reports from a table, evaluation of a complex query that involves multiple instances of a relation, and batch processing of a set of queries. In this paper, we study how to optimize multiple sortings of a table. We investigate the correlation between sort orders and exploit sort-sharing techniques of reusing the (partial) work done to sort a table on a particular order for another order. Specifically, we introduce a novel and powerful evaluation technique, called cooperative sorting, that enables sort sharing between seemingly non-related sort orders. Subsequently, given a specific set of sort orders, we determine the best combination of various sort-sharing techniques so as to minimize the total processing cost. We also develop techniques to make a traditional query optimizer extensible so that it will not miss the truly cheapest execution plan with the sort-sharing (post-) optimization turned on. We demonstrate the efficiency of our ideas with a prototype implementation in PostgreSQL and evaluate the performance using both TPC-DS benchmark and synthetic data. Our experimental results show significant performance improvement over the traditional evaluation scheme.

State-of-the-art graphics processors provide high processing power and furthermore, the high programmability of GPUs offered by frameworks like CUDA (Compute Unified Device Architecture) increases their usability as high-performance co-processors for general-purpose computing. Sorting is well investigated in Computer Science in general, but (because of this new field of application for GPUs) there is a demand for high-performance parallel sorting algorithms that fit with the characteristics of the modern GPU-architecture. We present a high-performance in-place implementation of Batcher's bitonic sorting networks for CUDA-enabled GPUs. Therefore, we assigned compare/exchange operations to threads in a way that decreases low-performance global-memory access and makes efficient use of high-performance shared memory. This greatly increases the performance of this in-place, comparison-based sorting algorithm. Our implementation outperforms all other algorithms in our tests when sorting 64-bit keys. It is the fastest comparison-based GPU sorting algorithm for 32-bit keys, being only outperformed by (non-comparison-based) radix sort when sorting sequences larger than 223. Copyright © 2011 John Wiley & Sons, Ltd.

Sorting is one of the frequent used operations in computer science. Due to highly parallel computing nature of GPU architecture; it can be utilized for sorting purpose. We have considered the input array that is to be sorted in a 2D matrix form and applied a modified version of merge sort on that matrix. This modification leads to a much efficient sorting algorithm with reduced complexity. Therefore a lot of work has already been done to improve the efficiency of sorting algorithms. In this paper We have used the GPU architecture for solving the sorting problem.

The parallel computing on loosely coupled architecture has been evolved now days because of the availability of fast, inexpensive processors and advancements in communication technologies. The aim of this paper is to evaluate the performance of parallel merge sort algorithm on loosely coupled architecture and compare it with theoretical analysis [1].The parallel computational time complexity is O (p) [3] using p processes and one element in each process. It has been found that there is no major difference between theoretical performance analysis and the actual result.

Problem statement: Researchers focused their attention on optimally ad aptive sorting algorithm and illustrated a need to develop tools f or constructing adaptive algorithms for large class es of measures. In adaptive sorting algorithm the run time for n input data smoothly varies from O(n) to O(nlogn), with respect to several measures of disor der. Questions were raised whether any approach or technique would reduce the run time of adaptive sor ting algorithm and provide an easier way of implementation for practical applications. Approach: The objective of this study is to present a new method on natural sorting algorithm with a run time for n input data O(n) to O(nlogm), where m defines a positive value and surrounded by 50% of n . In our method, a single pass over the inputted data creates some blocks of data or buffers accordi ng to their natural sequential order and the order can be in ascending or descending. Afterward, a bottom up approach is applied to merge the naturally sorted subsequences or buffers. Additionally, a par allel merging technique is successfully aggregated in our proposed algorithm. Results: Experiments are provided to establish the best, wo rst and average case runtime behavior of the proposed method. The simulation statistics provide same harmony with the theoretical calculation and proof the method ef ficiency. Conclusion: The results indicated that our method uses less time as well as acceptable memory to sort a data sequence considering the natural order behavior and applicable to the realistic rese arches. The parallel implementation can make the algorithm for efficient in time domain and will be the future research issue.

This paper presents some commonly used algorithms and data structures using the Lisp language, functional programming style, and recursive thinking. Insertion sort, selection sort, quick sort, binary search tree, search, insertion, and deletion operations are presented. The algorithms are written in purely functional and recursive style using Lisp. Only a small subset of Lisp is used to write the algorithms. Various factors related to learning, teaching, and the curriculum are pointed out.

Efficient sorting is a key requirement for many computer science algorithms. Acceleration of existing techniques as well as developing new sorting approaches is crucial for many real-time graphics scenarios, database systems, and numerical simulations to name just a few. It is one of the most fundamental operations to organize and filter the ever growing massive amounts of data gathered on a daily basis. While optimal sorting models for serial execution on a single processor exist, efficient parallel sorting remains a challenge. In this paper, we present a hardware-optimized parallel implementation of the radix sort algorithm that results in a significant speed up over existing sorting implementations. We outperform all known General Processing Unit (GPU) based sorting systems by about a factor of two and eliminate restrictions on the sorting key space. This makes our algorithm not only the fastest, but also the first general GPU sorting solution.

An efficient GPU‐based sorting algorithm is proposed in this paper together with a merging method on graphics devices. The proposed sorting algorithm is optimized for modern GPU architecture with the capability of sorting elements represented by integers, floats and structures, while the new merging method gives a way to merge two ordered lists efficiently on GPU without using the slow atomic functions and uncoalesced memory read. Adaptive strategies are used for sorting disorderly or nearlysorted lists, large or small lists. The current implementation is on NVIDIA CUDA with multi‐GPUs support, and is being migrated to the new born Open Computing Language (OpenCL). Extensive experiments demonstrate that our algorithm has better performance than previous GPU‐based sorting algorithms and can support real‐time applications.

The present paper makes use of factorial experiments to assess software complexity using insertion sort as an example. A new modeling for insertion sort is proposed. It might be of interest to implement the methodology in quicksort and other advanced algorithms.

In this paper, we show implementation results of various algorithms that sort data encrypted with Fully Ho-momorphic Encryption scheme based on Integers. We analyze the complexities of sorting algorithms over encrypted data by considering Bubble Sort, Insertion Sort, Bitonic Sort and Odd-Even Merge sort. Our complexity analysis together with implementation results show that Odd-Even Merge Sort has better performance than the other sorting techniques. We observe that complexity of sorting in homomorphic domain will always have worst case complexity independent of the nature of input. In addition, we show that combining different sorting algorithms to sort encrypted data does not give any performance gain when compared to the application of sorting algorithms individually.

In computer science literature, sorting is an age-old theoretically interesting problem with great practical importance. In this paper, we discuss the effect on sorting when the comparisons are erroneous. Such an analysis would be in particular effective for secured cloud data which is Fully Homomorphically Encrypted (FHE) and the sorting is intended to be applied on the encrypted data. Although theoretically feasible, FHE is costly due to the underlying Recrypt operation, removal of which leads to erroneous computations. In this context, we consider a two-stage sorting called Lazysort. In this sort, the first phase is a layer of Bubble sort with reduced Recrypts, thus leading to erroneous comparisons. We provide analysis to show the effect of this error on the eventual window in which the correct location of an element lies. Assuming such a window in which the probability of an element to lie is almost one, we apply a second pass of insertion sort, which has an linear complexity for an almost sorted array. In this paper, we discuss about practical challenges of implementing such encrypted sorting while working with underlying encrypted processor. Finally, we show how our proposed method makes this sorting technique actually feasible and provide practical results to accompany the theoretical claims made to justify the windowed technique for implementing the LazySort algorithm on FHE data.

The main idea of Optimized Selection Sort Algorithm (OSSA) is based on the already existing selection sort algorithm, with a difference that old selection sort; sorts one element either smallest or largest in a single iteration while optimized selection sort, sorts both the elements at the same time i.e smallest and largest in a single iteration. In this study we have developed a variation of OSSA for two-dimensional array and called it Optimized Selection Sort Algorithms for Two-Dimensional arrays OSSA2D. The hypothetical and experimental analysis revealed that the implementation of the proposed algorithm is easy. The comparison shows that the performance of OSSA2D is better than OSSA by four times and when compared with old Selection Sort algorithm the performance is improved by eight times (i.e if OSSA can sort an array in 100 seconds, OSSA2D can sort it in 24.55 Seconds, and similarly if Selection Sort takes 100 Seconds then OSSA2D take only 12.22 Seconds). This performance is remarkable when the array size is very large. The experiential results also demonstrate that the proposed algorithm has much lower computational complexity than the one dimensional sorting algorithm when the array size is very large.