Search

This paper proposes a high-performance bidirectional architecture for the quasi-comparison-free sorting algorithm. Our architecture improves the performance of the conventional unidirectional architecture by reducing the total number of sorting cycles via bidirectional sorting along with two auxiliary methods. Bidirectional sorting allows the sorting tasks to be conducted concurrently in the high- and low-index parts of our architecture. The first auxiliary method is boundary finding, which shortens the range for index searching by finding the boundaries of the range. The second auxiliary method is queue storing, which stores each useful index in a queue in advance to reduce the number of miss cycles during index searching. The performance of our architecture highly depends on the distribution of input data. For each set of input data to be sorted, five Gaussian distributions of the input data and four standard derivations for each distribution were adopted in our experiments. The results show that at the expense of some additional area cost, the number of sorting cycles and the energy consumption are significantly reduced by our method.

An efficient partial sort algorithm that is less complex, and more practical to implement compared to existing partial sort algorithms especially for real time applications is presented. The proposed partial sort algorithm does not use pivots, but instead makes use of past sorting decisions to narrow the search for each new sorted element. A major advantage of the proposed partial sort algorithm is that its complexity and sorting time are fixed, and are not dependent upon the data to be sorted, unlike other algorithms. This makes it a good candidate for real time applications.

Determining the activity series of a collection of elements is a classic pedagogical experiment, in which pairs of elements are reacted to determine the relative rank ordering of their reactivity. Determining the optimal sequence of pairwise experiments that minimizes the total number of experiments corresponds to well-known comparison sorting algorithms in computer science. We describe relevant algorithms (insertion sort, binary insertion sort, merge sort, and merge insertion sort) and their application to the activity series problem and discuss ways that this connection can contribute to the introductory chemistry and computer science curricula. In addition to pedagogical interest, this illustrates a simple form of artificial intelligence for chemical experiment planning.

Computer and communication systems and networks deal with many cases that require rearrangement of data either in descending or ascending order. This operation is called sorting, and the purpose of an efficient sorting algorithm is to reduce the computational complexity and time taken to perform the comparison, swapping, and assignment operations. In this article, we propose an efficient mean-based sorting algorithm that sorts integer/non-integer data by making approximately the same length independent quasi-sorted subarrays. It gradually finds sorted data and checks if the elements are partially sorted or have similar values. The elapsed time, the number of divisions and swaps, and the difference between the locations of the sorted and unsorted data in different samples demonstrate the superiority of the proposed algorithm to the Merge, Quick, Heap, and conventional mean-based sorts for both integer and non-integer large data sets which are random or partially/entirely sorted. Numerical analyses indicate that the mean-based pivot is appropriate for making subarrays with approximately similar lengths. Also, the complexity study shows that the proposed mean-based sorting algorithm offers a memory complexity same as the Quick-sort and a time complexity better than the Merge, Heap, and Quick sorts in the best-case. It is similar to the Merge and Heap sorts in view of the time complexity of the worst-case much better than the Quick-sort while these algorithms experience identical complexity in the average-case. In addition to finding part by part incremental (or decremental) sorted data before reaching the end, it can be implemented by parallel processing the sections running at the same time faster than the other conventional algorithms due to having independent subarrays with similar lengths.

The Shell sort algorithm is one of the most practically effective in-place sorting algorithms. However, it is difficult to execute this algorithm with its intended running time complexity on data encrypted using fully homomorphic encryption (FHE), because the insertion sort in Shell sort has to be performed by considering the worst-case input data. In this paper, in order for the sorting algorithm to be used on the FHE data, we modify the Shell sort with an additional parameter $\alpha $ , allowing exponentially small sorting failure probability. For a gap sequence of powers of two, the modified Shell sort with input array length $n$ is found to have the trade-off between the running time complexity of $O(n^{3/2}\sqrt {\alpha +\log \log n})$ and the sorting failure probability of $2^{-\alpha }$ . Its running time complexity is close to the intended running time complexity of $O(n^{3/2})$ and the sorting failure probability can be made very low with slightly increased running time. Further, the near-optimal window length of the modified Shell sort is also derived via convex optimization. The proposed analysis of the modified Shell sort is numerically confirmed by using randomly generated arrays. For the practical aspect, our modification can be applied to any gap sequence, and we show that Ciura’s gap sequence, which is known to have good practical performance, is also practically effective when our modified Shell sort is applied. We compare our modified Shell sort with other sorting algorithms with the FHE over the torus (TFHE) library, and it is shown that this modified Shell sort has the best performance in running time among in-place sorting algorithms on homomorphic encryption scheme.

We studied on typical sorting algorithms, compared their efficiencies, and proposed and evaluated a new sorting algorithms. In this paper, for some typical sorting algorithms, the principle and properties of each algorithm are described, and a function-type program in C language is given. Numerical experiments were used to compare and evaluate the execution times of the three O(n2) sorting algorithms (i.e., Bubble sort, Insertion sort and Selection sort) and the three O(nlogn) sorting algorithms ( i.e., Quicksort, Heaposrt and Mergesort). Furthermore, we proposed a new algorithm called Binary search insertion sort, compared it with the conventional Insertion sort, and confirmed that it can sort at a high speed of about 68%.

The most used algorithm is the sorting algorithm. There have been many popping sorting algorithms that can be used, in this study researchers took three sorting algorithms namely Insertion Sort, Selection Sort, and Merge Sort. As for this study will analyze the comparison of execution time and memory usage by considering the number of enter data of each algorithm used. The data used in this study is ukhuwah NET network bandwidth usage data connected in the Faculty of Computer Science in the form of double data types. After implementing and analyzing in terms of execution time merge sort algorithm has a faster execution time in sorting data with an average execution time value of 108.593777 ms on the 3000 data count. While in the same amount of data for the most execution time is the Selection Sort algorithm with a large execution time of 144.498144 ms, in terms of memory usage with the amount of data3000 Merge Sort Algorithm has the highest memory usage compared to the other two algorithms which is 21,444 MB while the other two algorithms have a succession of memory usage of 20,837 MB and 20,325MB.

Sorting is essential for many scientific and data processing problems. It is significant to improve the efficiency of sorting. Taking advantage of specialized hardware, parallel sorting, e.g., sorting networks and linear sorters, implements sorting in lower time complexity. However, most of them are designed based on the parallelization of algorithms, lacking consideration of specialized hardware structures. In this article, we propose an extended nonstrict partially ordered set-based configurable linear sorter on field-programmable gate arrays (FPGAs). First, we extend nonstrict partial order to the binary tuple and n-tuple nonstrict partial orders. Then, the linear sorting algorithm is defined based on them, with the consideration of hardware performance. It has 4N/n time complexity varying from 4 to 2 N as the tuple size varies. The number of comparisons reduces to N/2 in binary tuple-based sorting, which is half of the state-of-the-art insertion linear sorting. Finally, we implement the linear sorter on FPGAs. It consists of multiple customizable micro-cores, named sorting units (SUs). The SU packages the storage and comparison of the tuple. All the SUs are connected into a chain with simple communication, which makes the sorter fully configurable in length, bandwidth, and throughput. They also act the same in each clock cycle, so that the achieved frequency of the sorter improves. In our experiment, the sorter achieves at most 660-MHz frequency, 5.6 Gb/s throughput, and 87 times speed-up compared with the quick sort algorithm on general processors., NSFC - National Natural Science Foundation of China(20160204022GX). publication February 28, 2020; date of current version April 21, 2020. This work was supported in part by the National Natural Science Foundation of China under Grant 61472159, Grant 61572227, and Grant 61772227, and in part by the Development Project of Jilin Province of China under Grant 20160204022GX, Grant 20170101006JC, Grant 20170203002GX, Grant 20180201045GX, Grant 2017C030-1, and Grant 2017C033

Divide and Conquer is a well-known technique for designing algorithms. Many of the existing algorithms are a product of this popular algorithm design technique. Such include Quick sort and Merge sort sorting algorithms. These two algorithms have been widely employed for sorting, however, determining the most efficient among the two has always been a contentious issue. Most of the existing literature have compared these algorithms using machine dependent factors such as computational complexity but few have employed machine independent factors such as internal/external sorting, algorithm complexity: best, average, and worst cases, memory usage, stability etc. This study intends to contribute to this discuss using both machine dependent and independent factors. The implementation was carried out in MATLAB programming environment and the internal system clock was set to keep track of the time required for sorting. Results obtained revealed that in terms of computational speed using array of small sizes, Quick sort algorithm is faster, though Merge sort algorithm is faster with array of large sizes. Also, both algorithms are of O(nlogn) best case and average case complexity while the worst case for quicksort is O(n2) and that of merge sort remains unchanged. In terms of stability, Quick sort is stable while Merge sort is not. Despite the excellent performance of Merge sort algorithm, the need for an auxiliary memory for sorting makes it less preferable than Quick sort algorithm for applications where a good cache locality is of paramount importance.

Many sorting algorithms have been developed to enhance the performance of important applications from different domains such as commercial commuting, operational research and scientific simulation. In this paper, we propose a new in-place sorting algorithm called OneByOne (OBO) sort. When compared to selection sort and bubble sort algorithms, OBO demonstrated faster run time at different array sizes. OBO also showed nearly equal performance when compared to the insertion sort algorithm.

Converting tool path geometries of a computer-aided design (CAD) file to computerized numerical control (CNC) commands is the core functionality of a computer aided manufacturing (CAM) software for wire electrical discharge machining (WEDM). The number of curve objects (such as lines and arcs) for a complex tool path can reach more than 20000. However, curve objects in a CAD file are sorted by drawing sequence instead of processing sequence, and slow sorting will cause an increase in elapsed time (more than 120 seconds accordingly) and a hanging consequence to the running of the embedded CNC system. Finding adjacencies of curve objects is a key step in curve sequence sorting. Conventional algorithms targeted at adjacencies traverse all vertexes of CAD files, whose complexity is O(n2). According to the characteristics of a WEDM processing path, Ana-Hash Table Sorting algorithm is proposed to reduce the elapsed sorting time. This algorithm classifies vertexes into corresponding buckets in advance according to the coordinates, and adjacencies are judged among specific buckets, so that most useless traversals can be avoided. The complexity of the algorithm is O(nlogn). Noticing that the sorting acceleration ratio varies widely in table parameters, the optimization of table generating rules is given. The proposed algorithm works efficiently when the number of buckets per row is 1% to 1.5% of the number of curve objects. And the elapsed sorting time can be dramatically reduced by 99% as compared to the conventional traversal algorithm.

Sorting is an essential operation which is widely used and is fundamental to some very basic day to day utilities like searches, databases, social networks and much more. Optimizing this basic operation in terms of complexity as well as efficiency is cardinal. Optimization is achieved with respect to space and time complexities of the algorithm. In this paper, a novel left-field N-dimensional cartesian spaced sorting method is proposed by combining the best characteristics of bucket sort, counting sort and radix sort, in addition to employing hashing and dynamic programming for making the method more efficient. Comparison between the proposed sorting method and various existing sorting methods like bubble sort, insertion sort, selection sort, merge sort, heap sort, counting sort, bucket sort, etc., has also been performed. The time complexity of the proposed model is estimated to be linear i.e. O(n) for the best, average and worst cases, which is better than every sorting algorithm introduced till date.

As a basic operation, sorting has a wide range of applications. Early research provides a variety of serial sorting algorithms to speed up sorting. However, these serial algorithms waste the parallel computing capacity of current computers. On the other hand, it is of vital importance to promote the speed of sorting large-scale data because of the boom in data science, while traditional sorting algorithms are no longer suitable due to its relatively long complexity. Consequently, we propose two parallel sorting algorithms, Parallel Quick Sort Algorithm (PQSA) and Merging Subarrays from Quick Sort Algorithm (MSQSA) to solve this problem. In the meantime, we carry out simulation experiments to evaluate their performance. The experiment results show that two sorting algorithms run faster than traditional serial sorting algorithms. Furthermore, with the number of total threads increasing, PQSA and MSQSA have shorter running time and higher parallel speedup. Most importantly, when data size grows, MSQSA becomes slightly faster than PQSA, which shows its stronger practicability in sorting massive data.

Definitive goal of various modern sorting algorithm is to re-arrange sequence of numbers or words in ascending or descending order. Compared to other exisiting sorting algorithms, the modern sorting algorithms used to provide execution time, running time and complexity based on the given number of inputs. Thus, the modern algoirithms helps us to know more about re-arranging or re-ordering numbers or words including how they fastly operate inputs in a specific manner of time. This paper focused on asymptotic analysis pertaining to the running time consumed by most recent sorting algorithms based on the number of elements in an array. Through computation of the running time, it is really possible to know how sorting algorithms tends to become not only efficient but also a manner its usefulness. Various contemporary sorting algorithms like gnome sort, shaker sort, radix sort, shell sort and comb sort have considered and being compared in this study.

In this study, we focus on data sorting, which is a basic arithmetic operation, and we present a sorting library that can be used with the OpenCL programming model for field-programmable gate arrays (FPGAs). Our sorting library is built by combining three hardware sorting algorithms. It consumes more than twice the overall hardware resources compared to the merge sort restructured for the OpenCL programming model for FPGAs. However, its operating frequency is 1.09x higher and its sorting throughput is three orders of magnitude greater than the baseline.

How can algorithmic bias be reduced? While algorithms can improve expert decision making, undetected biases in algorithms can deepen social divisions and inequities. Is Fast Insertion Sort competitive with other effective sorting algorithms? Fast Insertion Sort offers improved worst-case time complexity over Insertion Sort, while keeping Insertion Sort's benefits of being simple, stable, and adaptive. Though Fast Insertion Sort has been shown to have a lower runtime than Hoare's Quicksort in many cases, reimplementation is done to verify those results again in C++ and Python, comparing the runtimes of Fast Insertion Sort, Quicksort, and other sorting algorithms on random and partially sorted arrays of different sizes. The pros and cons of Fast Insertion Sort as well as other questions, flaws, insights, and directions for future work is elaborated on. How do physicians, hospitals, insurers, patient advocacies, and med-tech vendors compete to draw the line between legitimate and excessive reliance on medical AI in clinical care? If unsuccessful, patients’ health and privacy is at risk. While physicians are hopeful that clinical care will be improved by AI that is being integrated by hospitals, insurers, and med-tech vendors, physicians, patients, and patient advocacies are pushing for a better balance between human and computer involvement. Since patients desire personalized care by human physicians, AI can be applied to healthcare work to save time for better doctor-patient relationships. By using a more representative data set, bias can be reduced.

Parallel sorting algorithms order a set of elements USING MULTIPLE processors in order to enhance the performance of sequential sorting algorithms. In general, the performance of sorting algorithms are EVALUATED IN term of algorithm growth rate according to the input size. In this paper, the running time, parallel speedup and parallel efficiency OF PARALLEL bubble sort is evaluated and measured. Message Passing Interface (MPI) IS USED for implementing the parallel version of bubble sort and IMAN1 supercomputer is used to conduct the results. The evaluation results show that parallel bubble sort has better running time as the number of processors increases. On other hand, regarding parallel efficiency, parallel bubble sort algorithm is more efficient to be applied OVER SMALL number of processors.

The present work is dedicated to the methods of sorting data and analysis of their complexity. Thereare several reasons for analysis of algorithms. One of them is necessity to evaluate the boundary values for theamount of memory or time required by some algorithm for successful data processing. The sorting process canimplemented by various algorithms. The choice of algorithm depends on the structure of the data being processed. Inpractice two classes of sorting are used: external and internal. If the amount of input data fits within the range ofavailable internal RAM they say about the algorithms for internal sorting. But if the input data are stored in files, i.e.external memory, they say about external sorting.This work demonstrates the fundamental algorithms of internal soritng with quadratic time and quickalgorithms with О(n*logn) complexity. Quick sorting algorithms such as merge sorting and Hoare“s quicksortalgorithms are given. Also simpler methods of internal sorting such as exchange sort, Shell“s method, insertion andselection algorithms are discussed as well. The article describes the idea behind these methods, agorithms on whichthey are based, complexity of these algorithms and provides concrete examples of programs.

Sorting is the most fundamental operation in database system. There are many classical sorting algorithms and among them the most commonly-used sorting algorithm in modern database system is merge sort. Merge sort is an efficient, general-purpose, comparison-based sorting algorithm. As merge sort is based on a divide and conquer model, it has found wide use in parallel computing algorithms. In this study, the authors present an adaptive sorting algorithm based on merge sort which is called array sort. Array sort not only takes advantages of merge sort, but also simplify the merge step by using a tag array. The proposed implementation consists of three phases: tag array creation phase, tag array split phase and list merge phase. Instead of just evaluating array sort in a single thread environment, the authors also run their experiments on multi-thread to test how array sort performs.

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.

In the present computer system, the data processing aspect, occupies the enormous processing frequency, approximately has the nearly 50% above CPU processing time is USES in the sort data. It can be seen that the data sorting algorithm has a high requirement on its own execution speed, so it is particularly important to implement a fast and good sorting algorithm. In this paper. The traditional merge sort algorithm uses two-way merge sort, which needs the same size of auxiliary space and data to be sorted, so it is necessary to improve it. The traditional merge sort method and an improved in-situ merge algorithm based on hand method are introduced, which is devoted to providing theoretical basis for improving the traditional data sort method.

Aiming at the main sorting stage of known radar signals in the radar signal sorting system, using supervised learning algorithms in machine learning to replace the traditional sorting algorithms which based on pulse repetition interval. The experimental results show that the supervised learning algorithms can successfully sort overlapping multi-type radar pulse signals, and the sorting accuracy of some algorithms exceeded 95%. It is feasible to apply the supervised learning algorithm to the main sorting stage of known radar signals.

Sorting is a central problem in computer science and one of the key components of many applications. To the best of our knowledge, no reactive programming implementation of sorting algorithms has ever been presented. In this paper we present reactive implementations of so-called sorting networks. Sorting networks are networks of comparators that are wired up in a particular order. Data enters a sorting network along various input wires and leaves the sorting network on the same number of output wires that carry the data in sorted order. This paper shows how sorting networks can be expressed elegantly in a reactive programming language by aligning the visual representation of a sorting network with the canonical DAG representation of reactive programs. We use our own experimental language called Haai to do so. With a limited number of built-in higher-order reactive programs, we are able to express sorting networks for bubble sort, insertion sort, bitonic sort, pairwise sort and odd-even merge sort.

Sorting algorithms have been a subject of research. Throughout the years various sorting algorithms have been implemented and their performance has been evaluated by comparing the space and time complexity. In this paper the super sort sorting algorithm with time complexity O(nlogn) has been implemented with MPI and CUDA. The intention is to compare the time taken by super sort algorithm when executed sequentially using C program and the time taken when implemented using CUDA and MPI.

We propose an O(N logN) sorting method by Modified Merge Sort Method, which shows huge potential to sort big data sets, and even better potential to sort big data sets with a smaller range. Six sorting algorithms: Selection Sort, Insertion sort, Merge sort, Quick sort, Bubble Sort and Modified Merge Sort were implemented in C++ programming languages and tested for the random sequence input of length 100, 1000, 4000, 9000 on random numbers and the IPL Dataset.

Sorting of data is employed in numerous applications and plays a vital role in determining the overall performance, speed and power. There is much sorting technique's like the Bubble Sort, Quick Sort, Selection Sort, Insertion Sort, Merge Sort, Heap Sort etc. Out of these, the Merge sort works the best when sorting huge data sets. In this paper, five of these merge sorting algorithms namely serial merge sort, parallel merge sort, bitonic merge sort, odd-even merge sort and the modified merge sort are analyzed and comparison based on resource utilization, delay and area are made. These algorithms are designed and developed to work on FPGA's. They can be parallelized on the FPGA easily to get better performance. Based on the results the best algorithm for an application or problem instance can be selected.

In modern technology or practical application, all things are gradually arranged. Therefore, in this paper, we attempt to establish a new sorting algorithm and compare it with some other standard sorting algorithms by their execution times. We designed and developed a methodology that can be executed on random data, ordering data, and some specific data (data means integers value), which can provide the best result for Right Bounding Sort (RBS). The methodology is comparing the array's left value with the rightmost value. Under a particular condition, these two values are swapped, then left index increase, and after completing the first step, the right index decrease, and it continues up to array size. Though there are many sorting algorithms invented for sorting an array with specific time complexity, space complexity, and other factors, they have some limitations because there is no sorting that is perfect for all various types of data. Some are good for small ranges of value, some are vast ranges of data, some are stable, and some are unstable. This algorithm performs with Big-O(n2) time complexity and Big-O (1) space complexity. We see that our new sorting algorithms provide better solutions than some other existing sorting algorithms like the bubble sort, insertion sort, cycle sort, etc. On the experimental dataset in respect of time complexity.

Sorting a set of items is a task that can be useful by itself or as a building block for more complex operations. That is why a lot of effort has been put into finding sorting algorithms that sort large sets as fast as possible. But the more sophisticated and complex the algorithms become, the less efficient they are for small sets of items due to large constant factors. We aim to determine if there is a faster way than insertion sort to sort small sets of items to provide a more efficient base case sorter. We looked at sorting networks, at how they can improve the speed of sorting few elements, and how to implement them in an efficient manner by using conditional moves. Since sorting networks need to be implemented explicitly for each set size, providing networks for larger sizes becomes less efficient due to increased code sizes. To also enable the sorting of slightly larger base cases, we adapted sample sort to Register Sample Sort, to break down those larger sets into sizes that can in turn be sorted by sorting networks. From our experiments we found that when sorting only small sets, the sorting networks outperform insertion sort by a factor of at least 1.76 for any array size between six and sixteen, and by a factor of 2.72 on average across all machines and array sizes. When integrating sorting networks as a base case sorter into Quicksort, we achieved far less performance improvements, which is probably due to the networks having a larger code size and cluttering the L1 instruction cache. But for x86 machines with a larger L1 instruction cache of 64 KiB or more, we obtained speedups of 12.7% when using sorting networks as a base case sorter in std::sort. In conclusion, the desired improvement in speed could only be achieved under special circumstances, but the results clearly show the potential of using conditional moves in the field of sorting algorithms., arXiv admin note: substantial text overlap with arXiv:1908.08111

Quick Sort is considered as the fastest sorting algorithm among all the sorting algorithms. The idea of selecting a pivot was introduced in classical Quick Sort in 1962. This sorting algorithm takes favorably less time compared to other methods. It needs a complex time O(\( nlogn \)) for the best case and O(\( n^{2} \)) for worst-case which occurs when the input array is already sorted or reversely sorted. To reduce the worst-case complexity we provide a strong algorithm where it makes fewer comparisons and the time complexity after using this algorithm becomes a function of logarithm O(\( nlogn \)) for worst-case complexity. We experimentally evaluate our algorithms and compare them with classical algorithms and with other papers. The algorithm presented here has profound implications for future studies of handling worst-case complexity and may one day help to solve this occurrence of the fastest sorting method.

Sorting is an essential operation that takes place in arranging data in a specific order, such as ascending or descending with numeric and alphabetic data. There are various sorting algorithms for each situation. For applications that have incremental data and require e an adaptive sorting algorithm, the insertion sort algorithm is the most suitable choice, because it can deal with each element without the need to sort the whole dataset. Moreover, the Insertion sort algorithm can be the most popular sorting algorithm because of its simple and straightforward steps. Hence, the insertion sort algorithm performance decreases when it comes to large datasets. In this paper, an algorithm is designed to empirically improve the performance of the insertion sort algorithm, especially for large datasets. The new proposed approach is stable, adaptive and very simple to translate into programming code. Moreover, this proposed solution can be easily modified to obtain in-place variations of such an algorithm by maintaining their main features. From our experimental results, it turns out that the proposed algorithm is very competitive with the classic insertion sort algorithm. After applying the proposed algorithm and comparing it with the classic insertion sort, the time taken to sort a specific dataset was reduced by 23%, regardless of the dataset’s size. Furthermore, the performance of the enhanced algorithm will increase along with the size of the dataset. This algorithm does not require additional resources nor the need to sort the whole dataset every time a new element is added.

This paper is aimed at a comparative study of several sorting algorithms with the purpose of evaluating their relative performance when the input array is randomly generated from zero-truncated binomial and poisson distributions. The sorting algorithms to be investigated are quick sort, k-sort, heap sort and merge sort, all having the same average case complexity of O(NlogN). In practical statistical cases, sometimes it is not possible to record or know about the occurrences as they are limited to values which exist above or below a given limit or within a particular range. Such situations result in truncated distributions. The relative performance of the above-mentioned sorting methods was compared on the basis of ‘execution time’ and the ‘number of swapping’ for both the average and worst cases of different algorithms.

Following the footprints of what have been done with the algorithm Stacksort, we investigate the preimages of the map associated with a slightly less well known algorithm, called Queuesort. After having described an equivalent version of Queuesort, we provide a recursive description of the set of all preimages of a given permutation, which can be also translated into a recursive procedure to effectively find such preimages. We then deal with some enumerative issues. More specifically, we investigate the cardinality of the set of preimages of a given permutation, showing that all cardinalities are possible, except for 3. We also give exact enumeration results for the number of permutations having 0,1 and 2 preimages. Finally, we consider the special case of those permutations $\pi$ whose set of left-to-right maxima is the disjoint union of a prefix and a suffix of $\pi$: we determine a closed formula for the number of preimages of such permutations, which involves two different incarnations of ballot numbers, and we show that our formula can be expressed as a linear combination of Catalan numbers., Comment: 18 pages

Many efficient algorithms are based on sorting the input data, because sorting often makes solving the problem easier. This chapter discusses the theory and practice of sorting as an algorithm design tool. Section 4.1 first discusses three important sorting algorithms: bubble sort, merge sort, and counting sort. After this, we will learn how to use the sorting algorithm available in the C++ standard library. Section 4.2 shows how sorting can be used as a subroutine to create efficient algorithms. For example, to quickly determine if all array elements are unique, we can first sort the array and then simply check all pairs of consecutive elements. Section 4.3 presents the binary search algorithm, which is another important building block of efficient algorithms.

Quick sort is one of the most sought after algorithms, because if implemented properly quick sort could be much faster than its counterparts, merge sort and heapsort. The main crux of quick sort algorithm is the implementation of the partitioning operation. Nico Lomuto and C. A. R Hoare have put forth partitioning algorithms that have gained prominent significance. Despite this, one can always shed more light on this partially understood operation of partition. Sorting algorithms have been further developed to enhance its performance in terms of computational complexity, memory and other factors. The proposed method is the use of randomized pivot in the implementation of Lomuto partition and Hoare partition algorithms, respectively. It is analysed with and without a randomized pivot element. This paper presents a comparison of the performance of a quick sort algorithm in different cases using contrasting partition approaches with and without randomized pivot. The results provide a theoretical explanation for the observed behaviour and give new insights on behaviour of quick sort algorithm for different cases. The Hoare partition approach with randomized pivot gives best time complexity in comparison to the other cases.

Sorting is one of a classic problem in computer engineer. One well-known sorting algorithm is a Counting Sort algorithm. Counting Sort had one problem, it can’t sort a positive and negative number in the same input list. Then, Modified Counting Sort created to solve that’s problem. The algorithm will split the numbers before the sorting process begin. This paper will tell another modification of this algorithm. The algorithm called Parallel Counting Sort. Parallel Counting Sort able to increase the execution time about 70% from Modified Counting Sort, especially in a big dataset (around 1000 and 10.000 numbers).

Counting sort is one of the basic sorting algorithm in computer science which has a time complexity of $\mathcal{O}(N + K)$ where N is the number of elements and K is the maximum value among those N elements. It is superior when it comes to sort countable objects those come from a discrete set of values, such as bounded integers. But, it fails to provide efficiency if the range of K is significantly greater than N. For this reason, it is less used in practical fields of computer science though it has an extensive use as a sub-routine in other sorting algorithms. Several extension approaches on counting sort algorithm have been proposed in the literature but none of those aims to increase the limit of K. This paper proposed an extension of counting sort algorithm that is named Square Root Counting Sort (SRCS) which has an increased limit of K. Specifically, the proposed approach can handle the maximum value of K2 where the classic one is only able to solve K. The first phase of the approach is to prepare some blocks of elements using square root technique and then sort each of the blocks simultaneously to get final sorted array. The proposed extension of counting sort outperforms than classic counting sort as well as bubble, selection and insertion sort.

We present four high performance hybrid sorting methods developed for various parallel platforms: shared memory multiprocessors, distributed multiprocessors, and clusters taking advantage of existence of both shared and distributed memory. Merge sort, known for its stability, is used to design several of our algorithms. We improve its parallel performance by combining it with Quicksort. We present two models designed for shared memory MIMD (OpenMP): (a) a non-recursive Merge sort and (b) a hybrid Quicksort and Merge sort. The third model presented is designed for distributed memory MIMD (MPI) using a hybrid Quicksort and Merge sort. Our fourth model is designed to take advantage of the shared memory within individual nodes of todays cluster systems, and to eliminate all internal data transfers between different nodes, Our model implements a one-step MSD-Radix to distribute data in ten packets (MPI) while parallel cores of each node use Quicksort to sort their data partitions sequentially then merge and sort them in parallel employing the OpenMp. The performances of all developed models outperform the baseline performance. Hybrid Quicksort and Merge sort outperformed Hybrid Memory Parallel Merge Sort using Hybrid MSD-Radix and Quicksort in Cluster Platforms when sorting small size data, but with larger data the speedup of Hybrid Memory Parallel Merge Sort Using Hybrid MSD-Radix and Quicksort in Cluster Platforms becomes bigger and it keeps improving. The speedup of Distributed Memory Parallel Hybrid Quicksort and Merge Sort is the best.

The program implementation of sorting algorithms is obtained. The program realization of complex for comparison of sorting algorithms is obtained. Using the obtained tools, an analysis of algorithms for sorting by speed was performed depending on the number of members of the data array.

Sorting plays a crucial role in almost all algorithms that support data science applications. A quadratic sorting algorithm is one in which the time taken for the algorithm to sort a dataset grows as the square of the size of the dataset. This paper aims at developing a new quadratic sorting algorithm by addressing the limitations in existing sorting algorithms. We use the idea that an unsorted data sequence can be thought of as a set of disjoint sorted sequences of data items. This paper describes a novel approach to provide a solution towards an unsorted sequence of data items. We have compared our method with existing quadratic sorting algorithms to demonstrate its efficiency over other techniques.

In this paper, we present the work regarding the selection sorting technique for double ended selection sort. This sorting algorithm is both theoretical and programmatically analysis show that the introduce advance selection sort algorithm which enhances the performance of selection sort. It is much faster than the selection sort because of its selection of minimum and maximum elements simultaneously. Advance selection sort algorithm possibility of enhancing execution speed up to 30%. Code for this algorithm is written in C programming Language. So easy to understand the concept of this sorting algorithm by everyone because C is the popular language. Results and discusion show a higher level of performance for the sorting algorithm. It can theoretically prove that the algorithm can reduce steps with the selection short and will improve N2 sorts toward NlogN sort.

Sorting is the procedure of arranging the elements in ascending or descending order. Sorting algorithms are not only used in computer science but also in our day-to-day life to reduce complexity. For optimizing the use of other algorithms, efficient sorting is required. This paper makes a comparison between merge sort, quick sort, selection sort and insertion sort by their time complexities.

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.

In the past few years, researchers have introduced several sorting algorithms to enhance time complexity, space complexity, and stability. A double hashing methodology first collects statistics about element distribution and then maps between elements of the array and indexes based on the knowledge collected during the first hashing.

This Innovative Practice Work-in-Progress Paper presents an alternative approach to teach algorithms using design patterns. The traditional approach to teaching different algorithms is to introduce each algorithm as a stand-alone approach. For example, when one goes over different sorting algorithms, one may start with logically simpler sorts like bubble sort or selection sort, and progress to the more challenging algorithms like heap sort or merge sort. We argue that there is another way to introduce a family of algorithms – identify the design patterns common to a group of algorithms, introduce the patterns first, before differentiating one approach from another. In this way, we focus on overall constructs and operations required, rather than how to complete each one of the sorts separately.This approach allows for an abstract class, such as Sort, to be first identified from a top-down approach, followed by the introduction and identification of which design patterns an actual algorithm falls - say divide-and-conquer for merge sort. The advantage of the approach is to allow the student to explore new realizations of solutions to problems developed from the abstract class, rather than studying a specific implementation of an algorithm.

Sorting remains a quintessential problem in computer science; henceforth, considerable research has focused on optimizing runtime efficiency when sorting a collection of elements. Most algorithms for sorting objects are comparison-based. Bucket Sort and Radix Sort are non-comparison based sorting algorithms that can sort objects in linear time. In both cases, the corresponding array indices represent a hash for the object. Nevertheless, Radix Sort still requires an auxiliary array. In this paper, replacing Radix Sort's auxiliary array with a hash table is proposed. Use of a hash table in Radix Sort should avoid the calculations for the array and be better suited for handling objects. As with an array-based Radix sort, this hash-based approach should maintain linearity, thereby sorting objects more efficiently. Following successfully programming this novel sorting algorithm, as the number of elements increases, the runtime progresses linearly, not exponentially. Moreover, as the number of digits increases, the sorting runtime still lengthens linearly. Thus, a hash-based Radix sort is feasible and overcomes many issues associated with current sorting algorithms.

Sorting algorithm is an important branch in the image recognition field. In this field, the bitonic sort is one of the typical merge-based parallel sorting algorithms. To meet requirements of performance and power consumption, kinds of accelerator for sorting algorithm were proposed. In this work, an energy-efficient reconfigurable sorting accelerator is designed and integrated into one RISC-V SoC to prove the efficiency. Compared with sorting results on CPU, our accelerator can help achieve 462x times.

Research on sorting algorithms is a very core research field in computer science. Today, any advancement in sorting algorithms would lead to less time and space required to perform the sorting task. This paper discusses a newly proposed algorithm—‘ledger-based sorting algorithm’. It is basically an advancement to ‘counting sort’, but not exactly counting sort. The purpose of this paper is to reduce the time and space required for sorting when the numbers given to you belong to a particular range (0–n) and all of them are distinct. This paper also compares the newly proposed algorithm with insertion sort, bubble sort, selection sort, quick sort, merge sort and mainly counting sort through graphical time analysis of these algorithms. The paper especially compares counting sort algorithm with the proposed algorithm in terms of both time and space complexity.

Sorting is a technique to rearrange a given list of elements according to a comparison operator on the elements. There are a large number of Sorting Algorithms like Insertion Sort, Merge Sort, Bucket Sort, Shell Sort, etc. The efficiency of the sorting algorithm depends on many factors such as memory usage patterns (the number of times the sections of memory must be copied or swapped to and from the disk), the total number of comparisons and the time requirements for the algorithms to run. In this paper, a method is proposed which combines two sorting algorithms (Bucket Sort and Shell Sort) in a way that takes advantage of the strength of each to improve overall performance.

Analysis of the efficiency of sorting algorithms most often bound up to software simulation. In practical field real time operation needs a system of faster sorting operation because software sorting is less effective. With the advancement of VLSI design sorting algorithm can be easily implemented as a block in any system which can be effectively used when necessary. In this paper, three most common sorting algorithms bubble sort, selection sort and insertion sort algorithm will be implemented using Verilog HDL language. For all algorithms RTL (Register Transfer Level) diagram will be examined and associated timing diagram will be analyzed for worst case scenario. Then the comparative analysis for the algorithms will be given form the analysis and synthesis report and from some operating parameters. The algorithm which has better hardware performance can be used as a block in any system with parallelism.