  Sorting is one of the most basic algorithms, and developing highly parallel
sorting programs is becoming increasingly important in high-performance
computing because the number of CPU cores per node in modern supercomputers
tends to increase. In this study, we have implemented two multi-threaded
sorting algorithms based on samplesort and compared their performance on the
supercomputer Fugaku. The first algorithm divides an input sequence into
multiple blocks, sorts each block, and then selects pivots by sampling from
each block at regular intervals. Each block is then partitioned using the
pivots, and partitions in different blocks are merged into a single sorted
sequence. The second algorithm differs from the first one in only selecting
pivots, where the binary search is used to select pivots such that the number
of elements in each partition is equal. We compare the performance of the two
algorithms with different sequential sorting and multiway merging algorithms.
We demonstrate that the second algorithm with BlockQuicksort (a quicksort
accelerated by reducing conditional branches) for sequential sorting and the
selection tree for merging shows consistently high speed and high parallel
efficiency for various input data types and data sizes.
