13.Sorting

Sorting algorithms place the data elements of a list into a certain order. Sorting is foundational to modern data and information services, since the computational complexity of retrieving information from datasets can be significantly reduced if the dataset is in proper order. For example, sorting is often used to canonicalize the data for fast comparison and reconciliation between data lists. Also, the efficiency of many data-processing algorithms can be improved if the data is in certain order.

Because of their importance, efficient sorting algorithms have been the subject of many computer science research efforts. Even with these efficient algorithms, sorting large data lists is still time consuming and can benefit from parallel execution. Parallelizing efficient sorting algorithms is challenging and requires elaborate designs.

This chapter presents the parallel designs for two important types of efficient sorting algorithms: radix sort and merge sort. Most of the chapter is dedicated to radix sort; merge sort is discussed briefly on the basis of the parallel merge pattern that was covered in Chapter 12, Merge. Other popular parallel sorting algorithms, such as transposition sort and sampling sort, are also briefly discussed.

13.1 Background

Introduction

Sorting

A sorting algorithm arranges the elements of a list into a certain order.

The order to be enforced by a sorting algorithm depends on the nature of these elements. Examples of popular orders are numerical order for numbers and lexicographical order for text strings. More formally, any sorting algorithm must satisfy the following two conditions:

1. The output is in either nondecreasing or nonincreasing order. For nondecreasing order, each element is no smaller than the previous element according to the desired order. For nonincreasing order, each element is no larger than the previous element according to the desired order.
2. The output is a permutation of the input. That is, the algorithm must retain all of the original input elements while reordering them into the output.

In its simplest form, the elements of a list can be sorted according to the values of each element. For example, the list [5, 2, 7, 1, 3, 2, 8] can be sorted into a nondecreasing order output [1, 2, 2, 3, 5, 7, 8].

A more complex and common use case is that each element consists of a key field and a value field and the list should be sorted on the basis of the key field. For example, assume that each element is a tuple (age, income in thousands of dollars). The list [(30,150), (32,80), (22,45), (29,80)] can be sorted by using the income as the key field into a nonincreasing order [(30,150), (32,80), (29,80), (22,45)].

Taxonomy

stable and unstable algorithms

A stable sort algorithm preserves the original order of appearance when two elements have equal key value. An unstable sorting algorithm does not offer such a guarantee.

For example, when sorting the list [(30,150), (32,80), (22,45), (29,80)] into a nonincreasing order using income as the key field, a stable sorting algorithm must guarantee that (32, 80) appears before (29,80) because the former appear before the latter in the original input.

Stable algorithms are required if one wishes to use multiple keys to sort a list in a cascaded manner. For example, if each element has a primary key and a secondary key, with stable sorting algorithms, one can first sort the list according to the secondary key and then sort one more time with the primary key. The second sort will preserve the order produced by the first sort.

comparison-based and noncomparison-based algorithms

Comparison-based sorting algorithms cannot achieve better than $O(N\cdot logN)$ complexity when sorting a list of $N$ elements because they must perform a minimal number of comparisons among the elements. In contrast, some of the noncomparison-based algorithms can achieve better than $O(N\cdot logN)$ complexity, but they may not generalize to arbitrary types of keys. Both comparison-based and noncomparison-based sorting algorithms can be parallelized.

In this chapter we present a parallel noncomparison-based sorting (radix sort) as well as a parallel comparison-based sorting algorithm (merge sort).

Importance

Because of the importance of sorting, the computer science research community has produced a great spectrum of sorting algorithms based on a rich variety of data structures and algorithmic strategies. As a result, introductory computer science classes often use sorting algorithms to illustrate a variety of core algorithm concepts, such as big O notation; divide-and-conquer algorithms; data structures such as heaps and binary trees; randomized algorithms; best-, worst-, and average-case analysis; time-space tradeoffs; and upper and lower bounds. In this chapter we continue this tradition and use two sorting algorithms to illustrate several important parallelization and performance optimization techniques (Satish et al., 2009 [5]).

13.2 Radix Sort

13.8 Other Parallel Sort Methods

Odd-even Transposition Sort 奇偶转置排序

它首先对所有偶/奇索引对的键值进行并行比较，即从第一个偶索引开始，比较索引为 k 和 k+1 的键值。如果位置 k+1 处的键值小于位置 k 处的键值，则交换这两个键值的位置。接着，对所有奇/偶索引对的键值重复上述步骤，也就是从第一个奇索引开始，比较索引为 k 和 k+1 的键值。这两种交替进行的阶段会不断重复，直到两个阶段都完成且没有键值需要交换为止。

奇偶转置排序与串行冒泡排序算法十分相似，而且和冒泡排序一样，它在处理大型序列时效率较低，因为对于一个包含 $N$ 个元素的序列，它可能需要执行 $O(N^2)$ 的操作量。

转置排序采用固定的比较模式，当元素顺序错乱时就会对其进行交换。由于每一步比较的都是不重叠的键值对，因此它很容易实现并行化。

排序网络 Sorting Networks

有一种完整的排序方法类别，它们通过固定的比较模式对序列进行排序，且通常能以并行方式执行。这类方法通常被称为排序网络 sorting networks，其中最著名的并行排序网络是巴彻（Batcher）提出的双调排序和奇偶归并排序（Batcher，1968 [1]）。巴彻的算法适用于固定长度的序列，其效率高于奇偶转置排序——对于包含 $N$ 个元素的序列，仅需 $O(N\cdot lo{g}^{2}N)$ 次比较。尽管从渐近复杂度来看，这些算法的成本要高于归并排序等方法的 $O(N\cdot logN)$，但在实际应用中，由于其实现简单，它们往往是处理小型序列时最高效的方法。

Comparison-based Parallel Sort 基于比较的并行排序算法

大多数基于比较的并行排序算法并不采用排序网络所特有的固定比较集合，这类算法可大致分为两大类。

第一类算法会将未排序的输入数据划分成若干个数据块（tiles），先对每个数据块进行排序，然后通过合并这些数据块来生成最终输出，其大部分工作都集中在合并阶段。本章中介绍的归并排序就是这类算法的一个例子——大部分操作都在用于合并已排序数据块的归并树中进行。

第二类算法则将主要工作放在对未排序序列的划分上，使得划分后的合并过程相对简单。采样排序算法（Sample sort，Frazer 与 McKellar，1970[4]）是这类算法的典型代表。采样排序首先从输入数据中选取 $p-1$ 个键值（例如随机选取），对这些键值进行排序，然后用它们将输入数据划分成 $p$ 个桶（bucket），使得桶 $k$ 中的所有键值都大于任何序号小于 $k$ 的桶中的键值，且小于任何序号大于 $k$ 的桶中的键值。这一步骤类似于快速排序中双向划分的 $p$ 路扩展。以这种方式划分数据后，每个桶可以独立排序，而最终的排序结果只需按顺序拼接所有桶即可得到。对于那些必须分布在多个物理内存（包括单个节点中多个 GPU 的内存）中的超大型序列而言，采样排序往往是最高效的选择。在实际应用中，对键值进行过采样是一种常见做法，因为适度的过采样能以极高的概率得到均衡的分区（Blelloch 等人，1991[3]）。正如归并排序和采样排序分别是基于比较的排序中自底向上和自顶向下策略的典型代表，基数排序算法也可设计为遵循自底向上或自顶向下的策略。本章所介绍的基数排序更完整的名称是最低有效位（LSB）基数排序，更一般地说，是最低有效数字（LSD）基数排序。该算法的各个步骤从键值的最低有效位开始，逐步处理到最高有效位（MSD）。最高有效位（MSD）基数排序则采用相反的策略：首先使用最高有效位将输入数据划分到与该数位可能取值相对应的桶中，然后在每个桶内独立地对下一个最高有效位执行相同的划分操作。当处理到最低有效位时，整个序列便已完成排序。与采样排序类似，最高有效位基数排序通常更适合处理极大型序列。最低有效位基数排序的每一步都需要对数据进行全局重排，而最高有效位基数排序的每一步则是在数据中逐渐缩小的局部区域上进行操作。

排序算法的主要分类

排序算法的分类方式有多种，常见的分类维度包括比较方式、并行性、操作原理等。以下是主要分类框架：

1. 按是否基于比较划分
   • 基于比较的排序：通过比较元素大小来决定顺序（如冒泡排序、快速排序、归并排序等）。
   • 非比较的排序：不依赖元素间的直接比较，而是利用元素本身的特性（如数字的位数），例如基数排序、计数排序、桶排序。
2. 按并行性划分
   • 串行排序：算法步骤需依次执行，无法并行化（如传统冒泡排序、插入排序）。
   • 并行排序：可通过多线程 / 多处理器同时执行多个操作（如奇偶转置排序、并行归并排序、排序网络）。
3. 按操作原理划分
   • 交换排序：通过交换逆序元素实现排序（如冒泡排序、快速排序）。
   • 归并排序：将序列拆分后合并（如归并排序）。
   • 选择排序：每次选择最小 / 最大元素放到对应位置（如选择排序、堆排序）。
   • 分配排序：根据元素值分配到不同桶中再合并（如基数排序、桶排序）。
4. 其他特殊类别
   • 排序网络：一种固定比较模式的并行排序结构，通过预设的比较器网络实现排序（与具体输入无关）。

一、基于比较的排序（通过比较元素大小排序）

1. 交换排序

• 冒泡排序：通过重复交换相邻逆序元素，使最大元素 ” 冒泡 ” 到末尾。
  • 特点：简单但效率低，时间复杂度 O (n²)，稳定。
• 快速排序：选择基准元素，将序列分为小于和大于基准的两部分，递归排序。
  • 特点：平均效率高（O (n log n)），不稳定，实际应用中常用。

2. 选择排序

• 选择排序：每次从剩余元素中选最小 / 大值，放到对应位置。
  • 特点：简单，时间复杂度 O (n²)，不稳定。
• 堆排序：利用堆（完全二叉树）的特性，每次提取最大 / 小元素并调整堆。
  • 特点：时间复杂度 O (n log n)，不稳定，适合大数据量。

3. 插入排序

• 插入排序：将元素逐个插入到已排序序列的合适位置。
  • 特点：适合小规模数据，时间复杂度 O (n²)，稳定。
• 希尔排序：分组进行插入排序，逐步缩小间隔。
  • 特点：改进版插入排序，时间复杂度约 O (n¹.³)，不稳定。

4. 归并排序

• 归并排序：将序列拆分到最小单位，再合并为有序序列。
  • 特点：时间复杂度 O (n log n)，稳定，适合并行化（可作为并行排序基础）。

5. 并行比较排序

• 奇偶转置排序：并行比较偶 / 奇索引对、奇 / 偶索引对，交替进行。
  • 特点：并行化简单，时间复杂度 O (n²)，属于排序网络的一种简化形式。
  • 属于基于比较的排序（通过比较元素大小决定是否交换）。
  • 属于并行排序（每次可并行比较不重叠的元素对）。
  • 本质是交换排序的并行版本（类似冒泡排序的并行化）。
• 排序网络（如巴彻双调排序）：通过固定的比较器网络实现并行排序。
  • 特点：比较模式固定，适合硬件实现，时间复杂度 O (log²n)。
  • 属于基于比较的排序（核心是比较器的固定连接）。
  • 属于并行排序（所有比较器可同时工作，只要不冲突）。
  • 是一种特殊架构的排序，其比较模式固定，与输入数据无关（例如巴彻的双调排序、奇偶归并排序）。

二、非比较排序（不依赖元素比较，利用值特性）

1. 分配排序

• 计数排序：统计每个值的出现次数，再按顺序输出。
  • 特点：适合范围较小的整数，时间复杂度 O (n + k)（k 为值范围），稳定。
• 桶排序：将元素分配到多个桶中，桶内单独排序后合并。
  • 特点：效率依赖桶的分布，平均 O (n)，稳定。
• 基数排序：按数位（或字符）从低到高（LSD）或从高到低（MSD）排序。
  • 特点：适合数字 / 字符串，时间复杂度 O (d・n)（d 为数位），稳定。

总结分类表

分类维度	包含算法
基于比较	冒泡、快排、选择、堆排、插入、希尔、归并、奇偶转置排序、排序网络
非比较	计数排序、桶排序、基数排序
串行排序	冒泡、快排、选择、堆排、插入、希尔、归并（串行实现）
并行排序	奇偶转置排序、排序网络、并行归并排序、并行快排
稳定排序	冒泡、插入、归并、计数、桶排序、基数排序
不稳定排序	快排、选择、堆排、希尔排序

实际应用中，需根据数据规模、稳定性需求、是否并行等场景选择算法。例如，小规模数据常用插入排序，大规模数据常用快排或归并排序，并行场景可考虑排序网络或采样排序。

参考

1. Batcher, K.E., 1968. Sorting networks and their applications. In: Proceedings of the AFIPS Spring Joint Computer Conference.
2. Bell, N., Hoberock, J., 2012. Thrust: a productivity-oriented library for CUDA. GPU Computing Gems Jade Edition. Morgan Kaufmann, pp. 359 371.
3. Blelloch, G.E., Leiserson, C.E., Maggs, B.M., Plaxton, C.G., Smith, S.J., Zagha, M., 1991, A comparison of sorting algorithms for the Connection Machine CM-2. In: Proceedings of the Third ACM Symposium on Parallel Algorithms and Architectures.
4. Frazer, W.D., McKellar, A.C., 1970. Samplesort: a sampling approach to minimal storage tree sorting. Journal of ACM 17 (3).
5. Satish, N., Harris M., Garland, M., 2009. Designing efficient sorting algorithms for manycore GPUs. In: Proceedings of the IEEE International Symposium on Parallel and Distributed Processing.