Search

In this paper, we show how the theory of sorting networks can be applied to synthesize optimized general-purpose sorting libraries. Standard sorting libraries are often based on combinations of the classic Quicksort algorithm, with insertion sort applied as base case for small, fixed, numbers of inputs. Unrolling the code for the base case by ignoring loop conditions eliminates branching, resulting in code equivalent to a sorting network. By replacing it with faster sorting networks, we can improve the performance of these algorithms. We show that by considering the number of comparisons and swaps alone we are not able to predict any real advantage of this approach. However, significant speed-ups are obtained when taking advantage of instruction level parallelism and non-branching conditional assignment instructions, both of which are common in modern CPU architectures. Furthermore, a close control of how often registers have to be spilled to memory gives us a complete explanation of the performance of different sorting networks, allowing us to choose an optimal one for each particular architecture. Our experimental results show that using code synthesized from these efficient sorting networks as the base case for Quicksort libraries results in significant real-world speed-ups.

The combination of non-determinism and sorting is mostly associated with permutation sort, a sorting algorithm that is not very useful for sorting and has an awful running time. In this paper we look at the combination of non-determinism and sorting in a different light: given a sorting function, we apply it to a non-deterministic predicate to gain a function that enumerates permutations of the input list. We get to the bottom of necessary properties of the sorting algorithms and predicates in play as well as discuss variations of the modelled non-determinism. On top of that, we formulate and prove a theorem stating that no matter which sorting function we use, the corresponding permutation function enumerates all permutations of the input list. We use free theorems, which are derived from the type of a function alone, to prove the statement.

An algorithm is basically term vital part of Operations Research Methodology. There are many algorithms related to sorting, basically it is the operation of logically arrangement of records or elements and it can be used for the numerically data or alphabetically data. Sorting operation implemented in the Data Structure to make efficient searching of elements. The Sorting Algorithm, having the swap, comparison and assignment operations related to the direct complexity of an algorithm. In proposed sorting algorithms we used strategy of selection of the elements i.e. we have the functions called as MinOddFunction(collect the minimum odd value of list) and MinEvenFunction(collect the minimum even valued from list), these functions collect the values from list and compare with each other and freeze it and so on till array is empty. This algorithm has the time complexity in the worst case is O(n^2), where n is the size of data being sorted. In this proposed paper, we will conclude the time complexity on the basis of number of iterations, comparisons, memory time and other factors.

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.

Quicksort is one of the most popular sorting algorithms, it is based on a divide-and-conquer technique and has a wide acceptance as the fastest general-purpose sorting technique. Though it is successful in separating large partitions into small ones, quicksort runs slowly when it processes its small partitions, for which completing the sorting through using a different sorting algorithm is much plausible solution. This variant minimizes the overall execution time but it switches to a constant sorting algorithm at a constant cut-off point. To cope with this constancy problem, it has been suggested that a dynamic model which can choose the fastest sorting algorithm for the small partitions. The model includes continuation with quicksort so that the cut-off point is also more flexible. To implement this with an intelligent algorithm selection model, artificial neural networks are preferred due to their non-comparison, constant-time and low-cost architecture features. In spite of the fact that finding the best sorting algorithm by using a neural network causes some extra computational time, the gain in overall execution time is greater. As a result, a faster variant of quicksort has been implemented by using artificial neural network based algorithm selection approach. Experimental results of the proposed algorithm and the Several other fast sorting algorithms have been presented, compared and discussed. (C) 2012 Elsevier Inc. All rights reserved.

Sorting data is one of the main problems in computer science which studied vastly and used in several places. In several geometric problems, like problems on point sets or lines in the plane or Euclidean space with higher dimensions, the problem of sorting pairs of points based on the distance (between them is used. Using general sorting algorithms, sorting n 2) distances between n points can be done in O(n2 log n) time. Ofcourse, sorting (n2) independent numbers does not have a faster solution, but since we have dependency between numbers in this case, finding a faster algorithm or showing that the problem in this case has O(n2 log n) time complexity is interesting. In this paper, we try to answer this question.

This paper presents a new procedure for the nondominated sorting with constraint handling to be used in a multiobjective evolutionary algorithm. The strategy uses a sorting algorithm and binary search to classify the solutions in the correct level of the Pareto front. In a problem with objective functions, using solutions in the population, the original nondominated sorting algorithm, used by NSGA-II, has always a computational cost of in a naïve implementation. The complexity of the new algorithm can vary from in the best case and in the worst case. A experiment was executed in order to compare the new algorithm with the original and another improved version of the Deb’s algorithm. Results reveal that the new strategy is much better than other versions when there are many levels in Pareto front. It is also concluded that is interesting to alternate the new algorithm and the improved Deb’s version during the evolution of the evolutionary algorithm.

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.

We introduce a sorting scheme which is capable of efficiently sorting encrypted data without the secret key. The technique is obtained by focusing on the multiplicative depth of the sorting circuit alongside the more traditional metrics such as number of comparisons and number of iterations. The reduced depth allows much reduced noise growth and thereby makes it possible to select smaller parameter sizes in somewhat homomorphic encryption instantiations resulting in greater efficiency savings. We first consider a number of well known comparison based sorting algorithms as well as some sorting networks, and analyze their circuit implementations with respect to multiplicative depth. In what follows, we introduce a new ranking based sorting scheme and rigorously analyze the multiplicative depth complexity as $$\mathcal {O}\log N+\log \ell $$OlogN+logl, where N is the size of the array to be sorted and $$\ell $$l is the bit size of the array elements. Finally, we simulate our sorting scheme using a leveled/batched instantiation of a SWHE library. Our sorting scheme performs favorably over the analyzed classical sorting algorithms.

Sorting is a huge demand research area in computer science. One of the fundamental issues in computer science is how to order the data in lexicographic order. In practical application computing requires things to be in order. The performance of any computation depends on the sorting algorithms. A lot of sorting algorithm has been developed by many authors to enhance the performance in terms of complexity analysis, and most of author analysis the time complexity and auxiliary space complexity of the sorting algorithms but the total space complexity taken by the algorithms not evaluated yet. The total space complexity contains the primary and secondary memory required to store input and output data, memory required to hold the code and working space. The goal of this paper is to test the various existing sorting algorithms and to evaluate the total space complexity of various sorting algorithms on a standard dataset. Sorting algorithms are evaluated on four cases of standard dataset. The four cases of the dataset are random with repeated data, reverse sorted with repeated data, sorted with repeated data, and nearly sorted with repeated data, and we measure the performance of each sorting algorithm in each case.

Constraint based sorting is considered to be one of the fundamental topics of discussion in computer science. Even though a large number of sorting algorithms have already been proposed and verified, but still new algorithms are being developed with respect to emerging problem statements. As sorting is the common operation of many algorithms, so efficient sorting makes easy searching, arranging and locating the information. This paper introduces a novel in-place sorting algorithm which works under the restriction of the number of movements. The restriction of movement is element wise i.e. there is a constraint on the number of movements for a particular element. The proposed algorithm is useful when cost of moving each element is not same and we have to sort the list keeping in mind that elements with higher movement cost should be swapped lesser number of times. In this paper, the algorithm has been presented with time complexity, space complexity analysis and experimental results.

The complexity of multi-objective evolutionary algorithms based on the non-dominated principles mainly depends on finding non-dominated fronts. In order to reduce complexity and improve construction efficiency, this paper introduces a non-dominated set construction algorithm based on Two Dimensional Sequence (TSNS). When the non-dominated set closes to the Pareto optimal front, it always maintains one dimension by ascending order while the other dimension by descending order. In order to verify the effectiveness of the proposed algorithm, we integrate the algorithm into GA, DE, PSO, then we tested and compared it with classical benchmark functions. The experimental results indicate that the proposed algorithm performs better than NSGA-II in terms of the quality of solutions and the speed of convergence.

The generalized sorting problem is to find the first k largest elements among n input elements and to report them in a sorted order. In this paper, we propose a fast generalized sorting algorithm under the single hop wireless networks model with collision detection (WNCD). The algorithm is based on the maximum finding algorithm and the sorting algorithm. The key point of our algorithm is to use successful broadcasts to build broadcasting layers logically and then to distribute the data elements into those logic layers properly. Thus, the number of broadcast conflicts is reduced. We prove that the average time complexity required for our generalized sorting algorithm is Θ(k + log(n - k)). When k = 1, our generalized sorting algorithm does the work of finding maximum, and when k = n, it does the work of sorting. Thus, the analysis of our algorithm builds a connection between the two extremely special cases which are maximum finding and sorting.

A product network defines a class of topologies that are very often used such as meshes, tori, and hypercubes, etc. This paper proposes a generalized algorithm for fault-tolerant parallel sorting in product networks. To tolerate r - 1 faulty nodes, an r-dimensional product network containing faulty nodes is partitioned into a number of subgraphs such that each subgraph contains at most one fault. Our generalized sorting algorithm is divided into two steps. First, a single-fault sorting operation is presented to correctly performed on each faulty subgraph containing one fault. Second, each subgraph is considered a supernode, and a fault-tolerant multiway merging operation is presented to recursively merge two sorted subsequences into one sorted sequence. Our generalized sorting algorithm can be applied to any product network only if the factor graph of the product graph can be embedding in a ring. Further, we also show the time complexity of our sorting operations on a grid, hypercube, and Petersen cube. Performance analysis illustrates that our generalized sorting scheme is a truly efficient fault-tolerant algorithm.

We present a VLSI implementation of a hardware sorting algorithm for continuous data sorting. The device is able to continuously process an input data stream while producing a sorted output data stream. At each clock cycle, the device reads and processes a 48-bit word, 24 bits for the datum and 24 bits for the associated tag. The data stream is sorted according to the tags preserving the order of words with identical tags. Sequences up to 256 words are completely sorted and longer sequences are partially sorted. The maximum operation frequency is 50 Mwords/s. The architecture is based on a chain of identical elementary sorting units. A full custom design exploits the highly regular architecture to achieve high area and time performance. We describe the algorithm and give architectural details.

To perform searching operation we have different kinds of searching techniques. These all searching algorithms works on data, which are previously sorted. An efficient algorithm is required to make searching fast and efficient. This paper presents a new sorting algorithm named as “Find and Place Sorting Technique for Unique Numbers (FPSTUN)”. This FPSTUN is designed to perform sorting quickly and easily and also efficient as existing algorithms in sorting.

Nowadays the tasks of computations speed-up and/or their optimization are actual. Among the approaches on how to solve these tasks, a method applying approaches of parallelization and asynchronization to a sorting algorithm is considered in the paper. The sorting methods are ones of elementary methods and they are used in a huge amount of different applications. In the paper, we offer a method of an array sorting that based on a division into a set of independent adjacent pairs of numbers and their parallel and asynchronous comparison. And this one distinguishes the offered method from the traditional sorting algorithms (like quick sorting, merge sorting, insertion sorting and others). The algorithm is implemented with the use of Petri nets, like the most suitable tool for an asynchronous systems description.

We present a simple and general parallel sorting scheme, ZZ-sort, which can be used to derive a class of efficient in-place sorting algorithms on realistic parallel machine models. We prove a tight bound for the worst case performance of ZZ-sort. We also demonstrate the average performance of ZZ-sort by experimental results obtained on a MasPar parallel computer. Our experiments indicate that ZZ-sort can be incorporated into a distributed memory parallel computer system as a standard routine, and this routine is useful for space critical situations. Finally, we show that ZZ-sort can be used to convert a non-adaptive parallel sorting algorithm into an in-place and adaptive one by considering the problem of sorting an arbitrarily large input on fixed-size reconfigurable meshes.

Sorting algorithms find their application in many fields. One of their main uses is to organize databases. Classical applications of sorting algorithms often can not cope satisfactorily with large data sets or with unfavorable poses of sorted strings. Typically, in such situations, we try to use other methods or apply sorting process to reshuffled input data. Unfortunately, this approach complicates sorting process and often results in significant prolongation of the time. In this paper, the authors examined an algorithm dedicated to the problem of sorting large scale data sets. In the literature, there are no studies of such examples. These studies will allow to describe the properties of sorting methods for large scale data sets. Performed tests have shown superior performance of the examined algorithm, especially for large scale data sets. Changes sped up sorting of data with any arrangement of the input elements.

Currently the tasks of computations speed-up and/or their optimization are actual ones. Among the ways to solve these tasks is a method of parallelization and asynchroniza-tion of a sorting algorithm, which is considered in the article. We offer a sorting method that is based on the principle of dividing an array into a set of independent pairs of numbers and their parallel and asynchronous comparison, which distinguishes the offered method from the traditional sorting algorithms (like quick sorting, merge sorting, insertion sorting and others). The algorithm is realized with the use of Petri nets as the most suitable tool for describing asynchronous systems. Examples of its work are given. The performance of the algorithm is evaluated for the best and the worst cases. In the best case the algorithm is executed for 2 or 3 conditional tacks depending on an array partition into the pairs of adjacent elements. In the worst case –for n or 3n/2, where n is the number of elements. Parallelization and asynchronization principles, used during the algorithm construction, can also be used for different algorithms.

With the popularity of parallel database machines based on the shared-nothing architecture, it has become important to find external sorting algorithms which lead to a load-balanced computation, i.e., balanced execution, communication and output. If during the course of the sorting algorithm each processor is equally loaded, parallelism is fully exploited. Similarly, balanced communication will not congest the network traffic. Since sorting can be used to support a number of other relational operations (joins, duplicate elimination, building indexes etc.) data skew produced by sorting can further lead to execution skew at later stages of these operations. In this paper we present a load-balanced parallel sorting algorithm for shared-nothing architectures. It is a multiple-input multiple-output algorithm with four stages, based on a generalization of Batcher's odd-even merge. At each stage then keys are evenly distributed among thep processors (i.e., there is no final sequential merge phase) and the distribution of keys between stages ensures against network congestion. There is no assumption made on the key distribution and the algorithm performs equally well in the presence of duplicate keys. Hence our approach always guarantees its performance, as long asn is greater thanp 3, which is the case of interest for sorting large relations. In addition, processors can be added incrementally.

In this paper the different sorting algorithms execution time has been examined with different number of elements. Through this experimental result concluded that the algorithm which is working best way. The analysis and execution time has been analyzed and tabulated with the help of Microsoft Excel. The sorting problem has attracted a great deal of research, perhaps due to the complexity of solving it efficiently despite its simple, familiar statement. Sorting algorithms are prevalent in introductory computer science classes, where the abundance of algorithms for the problem provides a gentle introduction to a variety of core algorithm concepts. The main objective of this paper is finding the best sorting algorithm based upon the time complexity.

A sorting network is a mathematical model of an oblivious sorting algorithm - that is, a sorting algorithm in which all comparisons take place in a fixed order at predetermined positions in the list.The search for sorting networks of optimal size is an old problem. Asymptotically optimal networks of size O(n log n) are known, where n is the number of inputs, but the hidden constants are enormous. Genetic algorithms have been used to tackle this problem in a number of studies since the early 1990s, often focusing on the historically interesting case of 16 inputs. In this special case, the best known bound of 60 comparisons has been attained, but often through the use of a particular, highly structured, initial sequence of comparisons that narrows the search space by filtering out all but a small core of input sequences.We make explicit the concept of a filter - a fixed sequence of comparisons to be extended to a sorting network through a stochastic process - and present a new construction for any perfect square number of inputs. In the case of 9 inputs, we extend the filter to a sorting network of size 25, attaining the best known bound. For 16 and 25 inputs, we present a simple GA variant that extends the filter to produce small sorting networks with highly regular structure.

An algorithm is any well-defined procedure or set of instructions, that takes some input in the form of some values, processes them and gives some values as output. Sorting involves rearranging information into either ascending or descending order. Sorting is considered as a fundamental operation in computer science as it is used as an intermediate step in many operations. A new sorting algorithm namely ‘An Endto-End Bi-directional Sorting (EEBS) Algorithm’ is proposed to address the shortcomings of the current popular sorting algorithms. The goal of this research is to perform an extensive empirical analysis of the newly developed algorithm and present its functionality. The results of the analysis proved that EEBS is much more efficient than the other algorithms having O(n2 ) complexity, like bubble, selection and insertion sort..

We introduce an algorithm to determine when a sorting operation, such as stack-sort or bubble-sort, outputs a given pattern. The algorithm provides a new proof of the description of West-2-stack-sortable permutations, that is permutations that are completely sorted when passed twice through a stack, in terms of patterns. We also solve the long-standing problem of describing West-3-stack-sortable permutations. This requires a new type of generalized permutation pattern we call a decorated pattern., On introduit un algorithme qui détermine quand un opérateur de tri (tels que le tri par une pile, ou le tri-bulle) produit un motif donnè en sortie. Cet algorithme fournit une nouvelle preuve de la caractérisation des permutations 2-triables au sens de West (c'est-à-dire des permutations qui sont triées complètement par deux passages dans une pile) par des motifs interdits. On résout aussi le problème longtemps ouvert de la caractérisation des permutations 3-triables au sens de West. Ceci demande de définir un nouveau type de motifs généralisés, appelè motif décoré.

We present a parallel sorting algorithm and its proof which sorts a sequence of n elements in time O(log2n) with n/2 processors on an EREW-PRAM computational model. A sorting network directly implements the algorithm using O(n·log n)PEs. The algorithm is based on the elementary Compare-Exchange operation and has the advantage that it does not require a powerful computational model, uses the least amount of space for the sorting problem, has small constants and can be implemented directly on a sorting network. Furthermore, the architecture of the network is simple and makes no unrealistic technological assumptions.

Sorting is a well-known problem frequently used in many aspects in the world of computational applications. Sorting means arranging a set of records (or a list of keys) in some (increasing or decreasing) order. In this solution report, a complete graph structure based comparison sorting algorithm, CompleteGraphSort has been proposed that takes time Θ(n2) in the worst-case, where n is the number of records in the given list to be sorted.

In this paper we present a sorting algorithm for natural numbers, which uses the methodology of indexing of the array and insert that number into proper index of the array without performing any element comparisons and swapping. This algorithm efficiently to give a much better performance than the existing sorting algorithms of the O(n2) class, for large array size with same length of digits of input data.

The design and analysis of adaptive sorting algorithms has made important contributions to both theory and practice. The main contributions from the theoretical point of view are: the description of the complexity of a sorting algorithm not only in terms of the size of a problem instance but also in terms of the disorder of the given problem instance; the establishment of new relationships among measures of disorder; the introduction of new sorting algorithms that take advantage of the existing order in the input sequence; and, the proofs that several of the new sorting algorithms achieve maximal (optimal) adaptivity with respect to several measures of disorder. The main contributions from the practical point of view are: the demonstration that several algorithms currently in use are adaptive; and, the development of new algorithms, similar to currently used algorithms that perform competitively on random sequences and are significantly faster on nearly sorted sequences. In this survey, we present the basic notions and concepts of adaptive sorting and the state of the art of adaptive sorting algorithms.

Sorting is a very well known problem in computer science. It means arranging the data in either increasing or decreasing order. Here we present a new comparison based sorting algorithm whose complexity is theoretically shown to be O(n2).However graphs of total time taken by different sorting algorithms confirms the superiority of our algorithm over other existing similar algorithms. We have also proved the correctness of the proposed algorithm. The logic of this algorithm can be used for searching efficiently in a two dimensional array.

Sorting algorithms and the sorting itself is an important concept in computational field. In this research study, we are proposing a unique sorting algorithm, based on assuming the first value as smallest and comparing it with the rest of the list and assuming the last value as biggest and comparing it with the rest of the list. Running cost analysis and its results obtained after implementation are provided in graphical form with an objective to compare the efficiency of the proposed technique with some existing well known techniques of sorting.

In this paper we present a sorting algorithm, which uses the methodology of insertion sort efficiently to give a much better performance than the existing sorting algorithms of the O(n² ) class. We prove the correctness of the algorithm and give a detailed time complexity analysis of the algorithm. We also describe various applications of the algorithms.

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 divide-and-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.

The growing complexity of modern processors has made the development of highly efficient code increasingly difficult. A promising automatic code generation strategy is implemented by library generators. This approach has mainly been applied to scientific codes which can be optimized by identifying code characteristics that depend only on the target machine. In this paper, we study the generation of sorting routines whose performance also depends on the characteristics of the input data. We present two approaches to generate efficient sorting routines. First, we consider the problem of selecting the best "pure" sorting algorithm as a function of the characteristics of the input data. We used machine learning algorithms to compute a function for each target machine that, at runtime, is used to select the best algorithm. Our second approach generalizes the first approach and can build new sorting algorithms from a few primitive operations. We use genetic algorithms and a classifier system to build hierarchically-organized hybrid sorting algorithms. Our results show that the algorithms generated using this second approach are quite effective and perform significantly better than the many conventional sorting implementations we tested. In particular, the routines generated using the second approach performs better than the most popular libraries available today: IBM ESSL, INTEL MKL and the C+ + STL.

Data sorting is an important procedure with many applications in computer science. Thus, various methods that improve the performance of sorting algorithms have been published. Most existing algorithms mainly aim to achieve a faster processing time for sorting and require memory space to load all data in the set. Such designs can be a burden for small devices that have relatively insufficient resources. This paper proposes a new sorting method for mobile devices that finds the minimum and maximum values by reading only a portion of the data into memory, unlike existing methods that read all data into memory. This phase is repeated as often as necessary in accordance with the size of the data set. The min/max values that are determined are written at the start and end point of the data set in storage. As the process is repeated, sorting can take place even if a small amount of memory is available, such as when using a mobile device. In order to evaluate the proposed method, we implemented a prototype for a music recommendation system, and we conducted comparative experiments with representative sorting methods. The results indicate that the proposed method consumed significantly less memory, and we confirmed the effectiveness and potentiality of the proposed method.

This article introduces a new sorting algorithm substituting the value of elements into a function to predict their positions approximately. We focus on building the function which is the mapping relationship between element values and their corresponding sorted locations. Applying the theory of entropy, we can demonstrate that its time complexity is from O(n) to O(nlgn). Experiments also indicate that it can run faster than Quicksort for small and medium scale data.

We give experimental evidence for the benefits of order-preserving compression in sorting algorithms. While, in general, any algorithm might benefit from compressed data because of reduced paging requirements, we identified two natural candidates that would further benefit from order-preserving compression, namely string-oriented sorting algorithms and word-RAM algorithms for keys of bounded length. The word-RAM model has some of the fastest known sorting algorithms in practice. These algorithms are designed for keys of bounded length, usually 32 or 64 bits, which limits their direct applicability for strings. One possibility is to use an order-preserving compression scheme, so that a bounded-key-length algorithm can be applied. For the case of standard algorithms, we took what is considered to be the among the fastest nonword RAM string sorting algorithms, Fast MKQSort, and measured its performance on compressed data. The Fast MKQSort algorithm of Bentley and Sedgewick is optimized to handle text strings. Our experiments show that order-compression techniques results in savings of approximately 15% over the same algorithm on noncompressed data. For the word-RAM, we modified Andersson's sorting algorithm to handle variable-length keys. The resulting algorithm is faster than the standard Unix sort by a factor of 1.5 X . Last, we used an order-preserving scheme that is within a constant additive term of the optimal Hu--Tucker, but requires linear time rather than O ( m log m ), where m = |Σ| is the size of the alphabet.

Consider a compare-swap operation that compares and possibly swaps the values of its two operands (a, b), so that we obtain a pair (a, b) satisfying a ≤ b after execution. A sorting network is a sequence of compare-swap operations that depends only on the number of elements to be sorted [1]. Let's call the compare-swap operation as a comparator. An advantage of sorting networks against the classical sorting algorithms is that the number of comparators is fixed for a given number of inputs. Thus they can be easily implemented in hardware. Figure 1 shows an example of a three-input sorting network and its alternative symbol.

We live in an era of data explosion that necessitates the discovery of novel out-of-core techniques. The I/O bottleneck has to be dealt with in developing out-of-core methods. The parallel disk model (PDM) has been proposed to alleviate the I/O bottleneck. Sorting is an important problem that has ubiquitous applications. Several asymptotically optimal PDM sorting algorithms are known and now the focus has shifted to developing algorithms for problem sizes of practical interest. In this paper we present several novel algorithms for sorting on the PDM that take only a small number of passes through the data. We also present a generalization of the zero-one principle for sorting. A shuffling lemma is presented as well. These lemmas should be of independent interest for average case analysis of sorting algorithms as well as for the analysis of randomized sorting algorithms.

Sorting is a well-known problem frequently used in many aspects of the world of computational application. Sorting means arranging a set of records (or a list of keys) in some (increasing or decreasing) order. In this paper, we propose a graph based sorting algorithm, designated as ARKEPIanGraphSort that takes time /spl otimes/(n/sup 2/) in the worst-case, where n is the number of records in the given list to be sorted.

We study several tested cases of the error-correcting graph isomorphism problem. The set Sn of n! permutations on n items is the search space for this optimization problem. We apply MA-sorting. This is a memetic algorithm with domain-independent mutation operators based on classical sorting. Each sorting algorithm works on results to a comparison predicate and defines a path in SI.,. In MA-sorting the mutation operator is a local-search that evaluates permutations suggested by the sorting algorithm. When such evaluation results in an improvement, the mutation is accepted and the comparison operator of the sorting algorithm evaluates to true. In contrast with previous proposals, our MA-sorting instantiated with selection sort finds optimal solutions for this case study.

A sorting algorithm is adaptive if its run time, for inputs of the same size n, varies smoothly from O (n) to O( n log n) as the disorder of the input varies. It is well accepted that files that are already sorted are often sorted again and that nearly sorted files often occur. Recently, rr:searchers have focused their attention on sorting algorithms that are optimally adaptive with rewect to several measures of disorder, since the type of disorder in the input is usually not kncwn. They have demonstrated a need to develop tools for the construction of sorting algorithms that are adaptive with respect to large classes of measures. We present Partition Sort, a new generic sorting algorithm for which wi: can establish adaptivity. It is based on divide-and-conquer in which the number of subproblem!r i t each level of recursion depends on the disorder of the input. We apply this generic algorithm to obtain optimal adaptivity for several measures of disorder. In addition, we introduce Randomized Partition Sort...

A simple computing model for sorting an arbitrary number of elements using a fixed-size sorting device is proposed, and a framework for designing a class of parallel sorting algorithms under this model is presented.

We present a simple and general parallel sorting scheme, ZZ-sort, which can be used to derive a class of efficient in-place sorting algorithms on realistic parallel machine models. We prove a tight bound for the worst case performance of ZZ-sort. We also demonstrate the average performance of ZZ-sort by experimental results obtained on a MasPar parallel computer. Our experiments indicate that ZZ-sort can be incorporated into a distributed memory parallel computer system as a standard routine, and this routine is useful for space critical situations. Finally, we show that ZZ-sort can be used to convert a non-adaptive parallel sorting algorithm into an in-place and adaptive one by considering the problem of sorting an arbitrarily large input on fixed-size reconfigurable meshes.

A multiple instruction stream-multiple data stream (MIMD) computer is a parallel computer with a large number of identical processing elements. The essential feature that distinguishes each MIMD computer family is the interconnection network. In this paper, we are concerned with two representative types of interconnection networks that are called the hypercube and the chordal ring networks. A family of regular graphs is presented as a possible candidate for the implementation of a distributed system and for fault-tolerant architecture. The symmetry of these graphs makes it possible to determine message routing by using a simple distributed algorithm. Arbitrary data permutations are generally accomplished by sorting. For certain classes of permutations, however, (for example, many frequently used permutations in parallel processing, such as bit reversal, bit shuffle, bit complement, matrix transpose, butterfly permutations in FFT algorithms, and segment shuffles), there are algorithms that are more efficient than the best sorting algorithm. One of these is the bit permute complement (BPC) class of permutations. We have developed algorithms for bidirectional networks. The developed algorithm in hypercube networks requires only 1 token memory register in each node. The algorithm takes the same number of steps as the maximum Hamming distance. Therefore, we have concluded that the presented algorithm is the optimal one. On the other hand, the developed algorithm in chordal ring networks requires 2 token storage register. The number of required routing steps in two kinds of networks is evaluated.

This paper compares the worst-case performance of eight standard sorting algorithms. It investigates how well-suited these algorithms are for hard real-time systems. In a series of experiments, we determined the average and worst-case execution times of the sorting algorithms for different numbers of elements to be sorted (in the range between 7 and 1000 elements). Average times were extracted from test runs with random data, whereas the worst-case times were determined both analytically with an analysis tool and experimentally by construction of the worst-case input data for each algorithm. The experiments demonstrate that algorithms that are well-suited for normal needs are not necessarily suited for hard real-time systems. Thus, the results help to choose the right sorting algorithm for real-time applications.

We present the design and implementation of a parallel out-of-core sorting algorithm, which is based on Leighton's columnsort algorithm. We show how to relax some of the steps of the original columnsort algorithm to permit a faster out-of-core implementation. Our algorithm requires only 4 passes over the data, and a 3-pass implementation is possible. Although there is a limit on the number of records that can be sorted—as a function of the memory used per processor—this upper limit need not be a severe restriction, and it increases superlinearly with the per-processor memory. To the best of our knowledge, our implementation is the first out-of-core multiprocessor sorting algorithm whose output is in the order assumed by the Parallel Disk Model. We define several measures of sorting efficiency and demonstrate that our implementation's sorting efficiency is competitive with that of NOW-Sort, a sorting algorithm developed to sort large amounts of data quickly on a cluster of workstations.

Sorting is one of the most common and important computing operations. In analyzing and comparing sorting algorithms, we consider their execution times, as indicated by the number of operations they execute as they sort n elements. The simplest algorithms have times that grow approximately as n 2 , while more complex algorithms offer times that grow approximately as n log n . This paper pursues a contrary goal: a sorting algorithm whose time grows more quickly than that of the well-known algorithms. The paper exhibits and analyzes such an algorithm.

Sorting is one of a set of fundamental problems in computer science. In this paper we present the first wait-free algorithm for sorting an input array of size N using P ≤ N processors to achieve optimal running time. We show two variants of the algorithm, one deterministic and one randomized, and prove that, with high probability, the latter suffers no more than $O(\sqrt{P})$ contention when run synchronously. Known sorting algorithms, when made wait-free through previously established transformation techniques, have complexity O(log 3 N) . The algorithm we present here, when run in the CRCW PRAM model, executes with high probability in O(log N) time when P=N , and O((Nlog N)/P) otherwise, which is optimal amongst comparison-based sorting algorithms. The wait-free property guarantees that the sort will complete despite any delays or failures incurred by the processors. This is a very desirable property from an operating systems point of view, since it allows oblivious thread scheduling as well as thread creation and deletion, without fear of losing the algorithm's correctness.