## 9.6 Other Sorting AlgorithmsAs mentioned in the introduction to this chapter, there are many sorting algorithms, and we cannot explore them all in this chapter. However, in this section we briefly present two additional sorting algorithms that are important both practically and theoretically. Our discussion of these schemes will be brief. Refer to the bibliographic remarks (Section 9.7) for references on these and other algorithms. ## 9.6.1 Enumeration SortAll the sorting algorithms presented so far are based on compare-exchange operations. This section considers an algorithm based on enumeration sort, which does not use compare-exchange. The basic idea behind enumeration sort is to determine the rank of each element. The rank of an element a Assume that concurrent writes to the same memory location of the CRCW PRAM result in the sum of all the values written being stored at that location (Section 2.4.1). Consider the n ## Algorithm 9.7 Enumeration sort on a CRCW PRAM with additive-write conflict resolution.1. procedure ENUM SORT (n) 2. begin 3. for each process P ## 9.6.2 Radix SortThe radix sort algorithm relies on the binary representation of the elements to be sorted. Let b be the number of bits in the binary representation of an element. The radix sort algorithm examines the elements to be sorted r bits at a time, where r < b. Radix sort requires b/r iterations. During iteration i , it sorts the elements according to their i Consider a parallel formulation of radix sort for n elements on a message-passing computer with n processes. The parallel radix sort algorithm is shown in Algorithm 9.8. The main loop of the algorithm (lines 3-17) performs the b/r enumeration sorts of the r-bit blocks. The enumeration sort is performed by using the prefix_sum() and parallel_sum() functions. These functions are similar to those described in Sections 4.1 and 4.3. During each iteration of the inner loop (lines 6-15), radix sort determines the position of the elements with an r-bit value of j . It does this by summing all the elements with the same value and then assigning them to processes. The variable rank holds the position of each element. At the end of the loop (line 16), each process sends its element to the appropriate process. Process labels determine the global order of sorted elements. ## Algorithm 9.8 A parallel radix sort algorithm, in which each element of the array A[1...n] to be sorted is assigned to one process. The function prefix sum() computes the prefix sum of the flag variable, and the function parallel sum() returns the total sum of the flag variable.1. procedure RADIX SORT(A, r) 2. begin 3. for i := 0 to b/r - 1 do 4. begin 5. offset := 0; 6. for j := 0 to 2 As shown in Sections 4.1 and 4.3, the complexity of both the parallel_sum() and prefix_sum() operations is Q(log n) on a message-passing computer with n processes. The complexity of the communication step on line 16 is Q(n). Thus, the parallel run time of this algorithm is |