China
Africa
Explore chapters and articles related to this topic
Parametric Mesh Generation for Optimization
Published in S. Ratnajeevan H. Hoole, Yovahn Yesuraiyan R. Hoole, Finite Elements-based Optimization, 2019
S. Ratnajeevan H. Hoole, Yovahn Yesuraiyan R. Hoole
Sorting is a technique that arranges the elements in a certain order. There are many sorting algorithms such as counting sort, bucket sort, radix sort, merge sort, heapsort, quicksort, etc. (Cormen et al., 2011). Each algorithm has its own advantages. Merge sort is one of the best sort algorithms which has n log (n) time complexity for each average, best, and worst case time complexities (ibid.). Another very important reason for selecting merge sort is that this algorithm is easily parallelizable – parallelization on the GPU is the main theme taken up in a subsequent chapter. Figure 7.21 (Merge Sort, n.d.) describes the merge sort in a graphical way. First, the list is split into two pieces and then each is split into two further pieces. This process is repeated until arriving at the singleton list. Then we work our way back up the recursion by merging together the short arrays into larger arrays. Algorithms 7.2 and 7.3 describe merge sort.
Introduction
Published in Randall L. Eubank, Ana Kupresanin, Statistical Computing in C++ and R, 2011
Randall L. Eubank, Ana Kupresanin
Mergesort is an order nlogn method (Exercise 9.9). Its worst-case efficiency is also O(nlogn) as compared to n2 for quicksort. The disadvantage of mergesort is the need for temporary storage when sorting arrays. Linked lists are another story. In that case the use of pointers makes it possible to dodge the extra storage requirement as we will eventually illustrate.
Polynomial Time Algorithms
Published in Craig A. Tovey, Linear Optimization and Duality, 2020
Of course, n items can be sorted in O(n2) time by repeatedly selecting the item that comes first from amongst the unselected items. Question: Why is this O(n2)?6 Several algorithms such as mergesort and heapsort sort in O(nlogn) time, which is significantly faster. Mergesort operates on a list of n numbers by splitting the list into two sublists of length ⌊n2⌋ and ⌈n2⌉, recursively sorting each sublist (say from least to largest), and then merging the two sorted sublists in time O(n) by repeatedly selecting and removing the least remaining number in either sublist, which takes O(1) time per selection because the only two possibilities are the first remaining element in each sublist. You will see how heapsort operates later in this chapter.
Big data processing with 1D-Crosspoint Arrays
Published in International Journal of Parallel, Emergent and Distributed Systems, 2023
Besides sorting networks, parallel versions of sorting algorithms have also been developed as general-purpose processors transitioned to multicore architectures. Examples include parallel Merge sort [1, p.159, p.385], [30], parallel Quicksort [31–33], and Bucket sort [34, p.77], [35, 36]. Some of these parallelized conventional algorithms were reported to have the theoretical minimum sorting time of for sorting n elements. However, similar to the AKS network, such algorithms have limitations in realistic scenarios. Cole's parallel merge sort is reported to be slower than Bitonic sorting networks due to high constant involved in the big-O notation [37], the parallel Quicksort requires a machine that is capable of concurrent write operation [32], and the -time parallel bucket sort can only sort integer elements [36].