一种归并排序方法及装置

摘要

本发明实施例提供了一种归并排序方法及装置，涉及数据处理技术领域。该方法包括：获取待归并排序数据形成的有序序列的数量；判断有序序列的数量与CAS的数量是否满足预设条件；若是，则对各有序序列进行分段，获取各有序序列的数据分段；通过CAS对每一个序列组中的有序序列的数据分段进行归并排序，获取每一个序列组对应的排序分段，任一序列组包括待归并排序的两个有序序列；按照归并排序的单调性要求，对每一个序列组对应的各排序分段进行排序，生成每一个序列组的归并排序结果。本发明实施例用于提升硬件资源利用率，以提升归并排序效率。

权利要求

1.一种归并排序方法，其特征在于，包括：获取待归并排序数据形成的有序序列的数量；

判断所述有序序列的数量是否小于比较交换单元CAS的数量的两倍；

若是，则对各有序序列进行分段，获取各有序序列的数据分段；

通过所述CAS对每一个序列组中的有序序列的数据分段进行归并排序，获取每一个序列组对应的排序分段，任一序列组包括待归并排序的两个有序序列；

按照归并排序的单调性要求，对每一个序列组对应的各排序分段进行排序，生成每一个序列组的归并排序结果。

2.根据权利要求1所述的方法，其特征在于，所述对各有序序列进行分段，包括：将每一个序列组中的第一有序序列均等的划分为N个第一数据分段，N为大于1的整数；

根据各第一数据分段的边界值，将各第一数据分段对应的第二有序序列划分为至少一个第二数据分段；

其中，任一第一数据分段对应的第二有序序列为划分得到该第一数据分段的第一有序序列所属的序列组中的另一个有序序列。

3.根据权利要求2所述的方法，其特征在于，所述通过所述CAS对每一个序列组中的有序序列的数据分段进行归并排序，包括：通过所述CAS对各第一数据分段和对应的第二数据分段进行归并排序，获取各数据分段的归并排序结果；

其中，任一第一数据分段对应的第二数据分段为与该第一数据分段具有交集的第二数据分段。

4.根据权利要求1所述的方法，其特征在于，所述对各有序序列进行分段，包括：将每一个有序序列均等的划分为M个数据分段；

其中，M为大于1的整数。

5.根据权利要求4所述的方法，其特征在于，所述通过所述CAS对每一个序列组中的有序序列的数据分段进行归并排序，包括：若第一数据分段和第二数据分段分别为同一序列组中的第一有序序列和第二有序序列的数据分段、所述第一数据分段的覆盖范围仅与所述第二数据分段的覆盖范围具有交集，且所述第二数据分段的覆盖范围仅与所述第一数据分段的覆盖范围具有交集，则通过所述CAS对所述第一数据分段和所述第二数据分段进行归并排序；

若第一数据分段和多个第二数据分段分别为同一序列组中的第一有序序列和第二有序序列数据分段、所述第一数据分段的覆盖范围仅与所述多个第二数据分段中的每一个第二数据分段的覆盖范围均有交集，且所述多个第二数据分段中每一个第二数据分段的覆盖范围都均仅与所述第一数据分段的覆盖范围具有交集，则拼接所述多个第二数据分段获取第三数据分段，并通过所述CAS对所述第一数据分段和所述第三数据分段进行归并排序；

若第一数据分段和第二数据分段为目标序列组中的第一有序序列的数据分段，第三数据分段和第四数据分段为目标序列组中的第二有序序列的数据分段，所述第一数据分段的覆盖范围仅与所述第三数据分段的覆盖范围、所述第四数据分段的覆盖范围均具有交集，且所述第二数据分段的覆盖范围仅与所述第四数据分段的覆盖范围具有交集，则根据所述第一数据分段的边界值将所述第四数据分段划分为第五数据分段和第六数据分段，将所述第五数据分段和第六数据分段中覆盖范围与所述第一数据分段的覆盖范围具有交集的数据分段与所述第三数据分段拼接为第七数据分段，并通过所述CAS对所述第一数据分段和所述第七数据分段进行归并排序，通过所述CAS对所述第二数据分段和所述第五数据分段和第六数据分段中覆盖范围与所述第二数据分段的覆盖范围具有交集的数据分段进行归并排序。

6.根据权利要求4所述的方法，其特征在于，所述方法还包括：若第一数据分段为目标序列组中的第一有序序列的数据分段，第二数据分段和第三数据分段依次为目标序列组中的第二有序序列的连续的两个数据分段，所述第一数据分段的覆盖范围位于所述第二数据分段的覆盖范围和所述第三数据分段的覆盖范围之间，则将第一数据分段拼接于所述第二数据分段之后或所述第三数据分段之前。

7.一种归并排序装置，其特征在于，包括：获取单元，用于获取待归并排序数据形成的有序序列的数量；

处理单元，用于判断所述有序序列的数量是否小于与比较交换单元CAS的数量的两倍；

分段单元，用于在所述有序序列的数量小于比较交换单元CAS的数量的两倍的情况下，对各有序序列进行分段，获取各有序序列的数据分段；

归并排序单元，用于通过所述CAS对每一个序列组中的有序序列的数据分段进行归并排序，获取每一个序列组对应的排序分段，任一序列组包括待归并排序的两个有序序列；

生成单元，用于按照归并排序的单调性要求，对每一个序列组对应的各排序分段进行排序，生成每一个序列组的归并排序结果。

8.一种电子设备，其特征在于，包括：存储器和处理器，存储器用于存储计算机程序；处理器用于在调用计算机程序时执行权利要求1‑6任一项所述的归并排序方法。

9.一种计算机可读存储介质，其特征在于，其上存储有计算机程序，计算机程序被处理器执行时实现权利要求1‑6任一项所述的归并排序方法。

说明书

一种归并排序方法及装置

技术领域

[0001] 本发明涉及数据处理技术领域，尤其涉及一种归并排序方法及装置。

背景技术

[0002] 随着科学技术的飞速发展，大数据储量规模持续保持40％左右的增长率，数据的爆炸式增长对数据处理带来了巨大的挑战。

[0003] 归并排序作为数据处理中最为基础且应用最为广泛的操作之一，在数据处理中具有非常重要的作用。归并排序算法的基本原理为：通过比较交换单元(Compare and Swap，
CAS)对两组有序序列中的数据进行比较，并输出较小或较大的数据，以获取该两组有序序
列的归并排序结果。针对数据规模动态变化的待归并排序数据，现有解决方法为基于CAS构
建归并树。归并树的每个父节点均包括两个子节点，父节点的输入为两个子节点对数据进
行归并排序后输出的归并排序结果(有序序列)，归并树的叶子节点输入的是初始数据序列
中的各数据或有序序列，归并树的根节点的输出为全部输入的最终归并排序结果。然而，归
并树的硬件资源利用率很低，CAS在大多数时间处于空闲状态。例如：在一个包括4层的归并
树通道中，当将原始数据输入该通道的第1层时，第1层的CAS处于工作状态时，该通道的第
2、3、4层的CAS处于空闲状态，当第1层将归并结果输入该通道的第2层后，第2层的CAS处于
工作状态时，该通道的第1、3、4层的CAS又会处于空闲状态。即，在归并树的一个通道中，同
时只有一层的CAS处于工作状态，其它层的CAS均处于空闲状态，硬件资源利用率较低，而硬
件资源利用率直接决定了归并排序的效率，因此如何提升硬件资源利用率，以提升归并排
序效率是一个亟待解决的问题。

发明内容

[0004] 有鉴于此，本发明提供了一种归并排序方法及装置，用于提升硬件资源利用率，以提升归并排序效率。

[0005] 为了实现上述目的，本发明实施例提供技术方案如下：

[0006] 第一方面，本发明的实施例提供一种归并排序方法，包括：

[0007] 获取待归并排序数据形成的有序序列的数量；

[0008] 判断所述有序序列的数量与比较交换单元CAS的数量是否满足预设条件；

[0009] 若是，则对各有序序列进行分段，获取各有序序列的数据分段；

[0010] 通过所述CAS对每一个序列组中的有序序列的数据分段进行归并排序，获取每一个序列组对应的排序分段，任一序列组包括待归并排序的两个有序序列；

[0011] 按照归并排序的单调性要求，对每一个序列组对应的各排序分段进行排序，生成每一个序列组的归并排序结果。

[0012] 作为本发明实施例一种可选的实施方式，所述对各有序序列进行分段，包括：

[0013] 将每一个序列组中的第一有序序列均等的划分为N个第一数据分段，N为大于1的整数；

[0014] 根据各第一数据分段的边界值，将各第一数据分段对应的第二有序序列划分为至少一个第二数据分段；

[0015] 其中，任一第一数据分段对应的第二有序序列为划分得到该第一数据分段的第一有序序列所属的序列组中的另一个有序序列。

[0016] 作为本发明实施例一种可选的实施方式，所述通过所述CAS对每一个序列组中的有序序列的数据分段进行归并排序，包括：

[0017] 通过所述CAS对各第一数据分段和对应的第二数据分段进行归并排序，获取各数据分段的归并排序结果；

[0018] 其中，任一第一数据分段对应的第二数据分段为与该第一数据分段具有交集的第二数据分段。

[0019] 作为本发明实施例一种可选的实施方式，所述对各有序序列进行分段，包括：

[0020] 将每一个有序序列均等的划分为M个数据分段；

[0021] 其中，M为大于1的整数。

[0022] 作为本发明实施例一种可选的实施方式，所述通过所述CAS对每一个序列组中的有序序列的数据分段进行归并排序，包括：

[0023] 若第一数据分段和第二数据分段分别为同一序列组中的第一有序序列和第二有序序列的数据分段、所述第一数据分段的覆盖范围仅与所述第二数据分段的覆盖范围具有
交集，且所述第二数据分段的覆盖范围仅与所述第一数据分段的覆盖范围具有交集，则对
所述第一数据分段和所述第二数据分段进行归并排序；

[0024] 若第一数据分段和多个第二数据分段分别为同一序列组中的第一有序序列和第二有序序列数据分段、所述第一数据分段的覆盖范围仅与所述多个第二数据分段中的每一
个第二数据分段的覆盖范围均有交集，且所述多个第二数据分段中每一个第二数据分段的
覆盖范围都均仅与所述第一数据分段的覆盖范围具有交集，则拼接所述多个第二数据分段
获取第三数据分段，并对所述第一数据分段和所述第三数据分段进行归并排序；

[0025] 若第一数据分段和第二数据分段为目标序列组中的第一有序序列的数据分段，第三数据分段和第四数据分段为目标序列组中的第二有序序列的数据分段，所述第一数据分
段的覆盖范围仅与所述第三数据分段的覆盖范围、所述第四数据分段的覆盖范围均具有交
集，且所述第二数据分段的覆盖范围仅与所述第四数据分段的覆盖范围具有交集，则根据
所述第一数据分段的边界值将所述第四数据分段划分为第五数据分段和第六数据分段，将
所述第五数据分段和第六数据分段中覆盖范围与所述第一数据分段的覆盖范围具有交集
的数据分段与所述第三数据分段拼接为第七数据分段，并通过所述CAS对所述第一数据分
段和所述第七数据分段进行归并排序，通过所述CAS对所述第二数据分段和所述第五数据
分段和第六数据分段中覆盖范围与所述第二数据分段的覆盖范围具有交集的数据分段进
行归并排序。

[0026] 作为本发明实施例一种可选的实施方式，所述方法还包括：

[0027] 若第一数据分段为目标序列组中的第一有序序列的数据分段，第二数据分段和第三数据分段依次为目标序列组中的第二有序序列的连续的两个数据分段，所述第一数据分
段的覆盖范围位于所述第二数据分段的覆盖范围和所述第三数据分段的覆盖范围之间，则
将第一数据分段拼接于所述第二数据分段之后或所述第三数据分段之前。

[0028] 作为本发明实施例一种可选的实施方式，所述判断所述有序序列的数量与CAS的数量是否满足预设条件，包括:

[0029] 判断所述有序序列的数量是否小于所述CAS的数量的两倍；

[0030] 若所述序序列的数量小于所述CAS的数量的两倍，则确定所述有序序列的数量与所述CAS的数量满足预设条件；

[0031] 若所述序序列的数量大于或等于所述CAS的数量的两倍，则确定所述有序序列的数量与所述CAS的数量不满足预设条件。

[0032] 第二方面，本发明实施例提供一种归并排序装置，包括：

[0033] 获取单元，用于获取待归并排序数据形成的有序序列的数量；

[0034] 处理单元，用于判断所述有序序列的数量与比较交换单元CAS的数量是否满足预设条件；

[0035] 分段单元，用于在所述有序序列的数量与比较交换单元CAS的数量满足预设条件的情况下，对各有序序列进行分段，获取各有序序列的数据分段；

[0036] 归并排序单元，用于通过所述CAS对每一个序列组中的有序序列的数据分段进行归并排序，获取每一个序列组对应的排序分段，任一序列组包括待归并排序的两个有序序
列；

[0037] 生成单元，用于按照归并排序的单调性要求，对每一个序列组对应的各排序分段进行排序，生成每一个序列组的归并排序结果。

[0038] 作为本发明实施例一种可选的实施方式，所述分段单元，具体用于将每一个序列组中的第一有序序列均等的划分为N个第一数据分段，N为大于1的整数；

[0039] 根据各第一数据分段的边界值，将各第一数据分段对应的第二有序序列划分为至少一个第二数据分段；

[0040] 其中，任一第一数据分段对应的第二有序序列为划分得到该第一数据分段的第一有序序列所属的序列组中的另一个有序序列。

[0041] 作为本发明实施例一种可选的实施方式，所述归并排序单元，具体用于通过所述CAS对各第一数据分段和对应的第二数据分段进行归并排序，获取各数据分段的归并排序
结果；

[0042] 其中，任一第一数据分段对应的第二数据分段为与该第一数据分段具有交集的第二数据分段。

[0043] 作为本发明实施例一种可选的实施方式，所述分段单元，具体用于将每一个有序序列均等的划分为M个数据分段；

[0044] 其中，M为大于1的整数。

[0045] 作为本发明实施例一种可选的实施方式，所述归并排序单元，具体用于若第一数据分段和第二数据分段分别为同一序列组中的第一有序序列和第二有序序列的数据分段、
所述第一数据分段的覆盖范围仅与所述第二数据分段的覆盖范围具有交集，且所述第二数
据分段的覆盖范围仅与所述第一数据分段的覆盖范围具有交集，则通过所述CAS对所述第
一数据分段和所述第二数据分段进行归并排序；

[0046] 若第一数据分段和多个第二数据分段分别为同一序列组中的第一有序序列和第二有序序列数据分段、所述第一数据分段的覆盖范围仅与所述多个第二数据分段中的每一
个第二数据分段的覆盖范围均有交集，且所述多个第二数据分段中每一个第二数据分段的
覆盖范围都均仅与所述第一数据分段的覆盖范围具有交集，则拼接所述多个第二数据分段
获取第三数据分段，并通过所述CAS对所述第一数据分段和所述第三数据分段进行归并排
序；

[0047] 若第一数据分段和第二数据分段为目标序列组中的第一有序序列的数据分段，第三数据分段和第四数据分段为目标序列组中的第二有序序列的数据分段，所述第一数据分
段的覆盖范围仅与所述第三数据分段的覆盖范围、所述第四数据分段的覆盖范围均具有交
集，且所述第二数据分段的覆盖范围仅与所述第四数据分段的覆盖范围具有交集，则根据
所述第一数据分段的边界值将所述第四数据分段划分为第五数据分段和第六数据分段，将
所述第五数据分段和第六数据分段中覆盖范围与所述第一数据分段的覆盖范围具有交集
的数据分段与所述第三数据分段拼接为第七数据分段，并通过所述CAS对所述第一数据分
段和所述第七数据分段进行归并排序，通过所述CAS对所述第二数据分段和所述第五数据
分段和第六数据分段中覆盖范围与所述第二数据分段的覆盖范围具有交集的数据分段进
行归并排序。

[0048] 作为本发明实施例一种可选的实施方式，所述处理单元，具体用于判断所述有序序列的数量是否小于所述CAS的数量的两倍；若所述序序列的数量小于所述CAS的数量的两
倍，则确定所述有序序列的数量与所述CAS的数量满足预设条件；若所述序序列的数量大于
或等于所述CAS的数量的两倍，则确定所述有序序列的数量与所述CAS的数量不满足预设条
件。

[0049] 第三方面，本发明实施例提供一种电子设备，包括：存储器和处理器，存储器用于存储计算机程序；处理器用于在调用计算机程序时执行第一方面或第一方面任一种可选的
实施方式所述的归并排序方法。

[0050] 第四方面，本发明实施例提供一种计算机可读存储介质，其上存储有计算机程序，计算机程序被处理器执行时实现第一方面或第一方面任一种可选的实施方式所述的归并
排序方法。

[0051] 第五方面，本发明实施例提供一种计算机程序产品，包括计算机程序/指令，该计算机程序/指令被处理器执行时实现第一方面或第一方面任一种可选的实施方式所述的归
并排序方法。

[0052] 本发明实施例提供的归并排序方法首先获取待归并排序数据形成的有序序列的数量，并在有序序列的数量与CAS的数量是否满足预设条件的情况下对各有序序列进行分
段，获取各有序序列的数据分段，然后通过所述CAS对每一个序列组中的有序序列的数据分
段进行归并排序，获取每一个序列组对应的排序分段，最后按照归并排序的单调性要求，对
每一个序列组对应的各排序分段进行排序，生成每一个序列组的归并排序结果。由于本发
明实施例提供的归并排序方法可以在有序序列的数量与CAS的数量是否满足预设条件的情
况下对各有序序列进行分段，并通过所述CAS对每一个序列组中的有序序列的数据分段进
行归并排序，因此本发明实施例提供的归并排序方法可以归并排序过程中减少处于空闲状
态的CAS的数量，提升硬件资源利用率，进而提升归并排序效率。

附图说明

[0053] 此处的附图被并入说明书中并构成本说明书的一部分，示出了符合本发明的实施例，并与说明书一起用于解释本发明的原理。

[0054] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，对于本领域普通技术人员而
言，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

[0055] 图1为本发明实施例提供的归并排序方法的步骤流程图之一；

[0056] 图2为本发明实施例提供的归并排序方法的步骤流程图之二；

[0057] 图3为本发明实施例提供的归并排序方式的示意图之一；

[0058] 图4为本发明实施例提供的归并排序结果的示意图；

[0059] 图5为本发明实施例提供的归并排序方法的步骤流程图之三；

[0060] 图6为本发明实施例提供的归并排序方式的示意图之二；

[0061] 图7为本发明实施例提供的归并排序方式的示意图之三；

[0062] 图8为本发明实施例提供的归并排序方式的示意图之四；

[0063] 图9为本发明实施例提供的归并排序方式的示意图之五；

[0064] 图10为本发明实施例提供的归并排序装置的结构示意图；

[0065] 图11为本发明实施例提供的电子设备的硬件结构示意图。

具体实施方式

[0066] 为了能够更清楚地理解本发明的上述目的、特征和优点，下面将对本发明的方案进行进一步描述。需要说明的是，在不冲突的情况下，本发明的实施例及实施例中的特征可
以相互组合。

[0067] 在下面的描述中阐述了很多具体细节以便于充分理解本发明，但本发明还可以采用其他不同于在此描述的方式来实施；显然，说明书中的实施例只是本发明的一部分实施
例，而不是全部的实施例。

[0068] 本发明的说明书和权利要求书中的术语“第一”和“第二”等是用于区别同步的对象，而不是用于描述对象的特定顺序。例如，第一操作和第二操作是用于区别不同的操作，
而不是用于描述操作的特定顺序。

[0069] 在本发明实施例中，“示例性的”或者“例如”等词用于表示作例子、例证或说明。本发明实施例中被描述为“示例性的”或者“例如”的任何实施例或设计方案不应被解释为比
其它实施例或设计方案更优选或更具优势。确切而言，使用“示例性的”或者“例如”等词旨
在以具体方式呈现相关概念。此外，在本发明实施例的描述中，除非另有说明，“多个”的含
义是指两个或两个以上。

[0070] 本发明实施例提供的归并排序方法的执行主体可以为归并排序装置。该归并排序装置可以为手机、平板电脑、笔记本电脑、超级移动个人计算机(ultra‑mobile personal 
computer，UMPC)、上网本、个人数字助理(personal digital assistant，PDA)、智能手表、
智能手环等终端设备，或者该终端设备还可以为其他类型的终端设备，本发明实施例对终
端设备的类型不作限定。

[0071] 本发明实施例的总的发明构思为：当待归并排序数据形成的有序序列的数量小于CAS的输入时，将有序序列拆分为至少两个数据分段，并通过CAS对各数据分段进行归并排
序，从而使更多CAS处于工作状态，提升硬件资源利用率，进而提升归并排序效率。

[0072] 本发明实施例提供了一种归并排序方法，参照图1所示，该归并排序方法包括如下步骤S11至S15：

[0073] S11、获取待归并排序数据形成的有序序列的数量。

[0074] 具体的，本发明实施中的有序序列是指对多个待归并排序数据进行归并排序后得到的数据序列，每一个有序序列中至少包括两个数据。例如：对数据“2”和数据“6”进行归并
排序后，可以得到有序序列“2 6”。再例如：对有序序列“2 5”和有序序列“3 6”进行归并排
序后，可以得到有序序列“2 3 5 6”。

[0075] S12、判断所述有序序列的数量与CAS的数量是否满足预设条件。

[0076] 作为本发明实施例一种可选的实施方式，上述步骤S12(判断所述有序序列的数量与CAS的数量是否满足预设条件)包括如下步骤a至步骤c：

[0077] 步骤a、判断所述有序序列的数量是否小于所述CAS的数量的两倍。

[0078] 在上述步骤a中，若所述序序列的数量小于所述CAS的数量的两倍，则执行入下步骤b，若所述序序列的数量大于或等于所述CAS的数量的两倍，则执行入下步骤c。

[0079] 步骤b、确定所述有序序列的数量与所述CAS的数量满足预设条件。

[0080] 步骤c、确定所述有序序列的数量与所述CAS的数量不满足预设条件。

[0081] 示例性的，以下以待归并排序数据的数量为1000万、CAS的数量为500为例对上述实施例提供的归并排序方法进行说明。

[0082] 第一轮归并排序、由于待归并排序数据的数量为1000万，因此将待归并排序数据首先拆分为1000万个数据，并将1000万个数据两两为一组输入一个CAS中形成一个数据长
度为2的有序序列。由于CAS的特性为将两个输入归并排序输出为1个数据，因此可以得到
500万个数据长度为2的有序序列。此时，有序序列的数量为500万，CAS的数量为500，因此无
需对有序序列进行分段，直接对有序序列进行下一次归并排序。

[0083] 第二轮归并排序、对500万个数据长度为2的有序序列进行归并排序，可以得到数据长度为4的250万个有序序列，此时，有序序列的数量为250万，CAS的数量为500，因此无需
对有序序列进行分段，直接对有序序列进行下一次归并排序。

[0084] 第n轮归并排序、可以得到数据长度为2n的1000万/2n个有序序列。当n>14时，2n>n
10000，1000万/2 <500*2，因此当完成第14轮归并排序后，确定所述有序序列的数量与CAS
的数量满足预设条件。

[0085] 在上述步骤S12中，若有序序列的数量与比较交换单元CAS的数量满足预设条件，则执行如下步骤S13。

[0086] S13、对各有序序列进行分段，获取各有序序列的数据分段。

[0087] 具体的，本发明实施例中的任一有序序列的数据分段为对该有序序列进行分段得到的全部数据分段。例如：对有序序列A进行分段，得到了数据分段a1和数据分段a2，则有序
序列A的数据分段包括：数据分段a1和数据分段a2。再例如：对有序序列B进行分段，得到了
数据分段b1、数据分段b2、数据分段b3以及数据分段b4，则有序序列B的数据分段包括：数据
分段b1、数据分段b2、数据分段b3以及数据分段b4。

[0088] S14、通过所述CAS对每一个序列组中的有序序列的数据分段进行归并排序，获取每一个序列组对应的排序分段。

[0089] 其中，任一序列组包括待归并排序的两个有序序列。

[0090] 具体的，在本发明实施例中一个序列组包括待归并排序的两个有序序列，序列组对应的排序分段为该序列组中的两个有序序列的各个数据分段的归并排序结果。例如：序
列组AB包括：有序序列A和有序序列B，有序序列A对应的数据分段包括数据分段a1和数据分
段a2，有序序列B对应的数据分段包括数据分段b1和数据分段b2，对数据分段a1和数据分段
b1进行归并排序，归并排序结果为排序分段ab1，对数据分段a2和数据分段b2进行归并排
序，归并排序结果为排序分段ab2，则序列组AB对应的排序分段包括：排序分段ab1和排序分
段ab2。

[0091] S15、按照归并排序的单调性要求，对每一个序列组对应的各排序分段进行排序，生成每一个序列组的归并排序结果。

[0092] 具体的，本发明实施例中归并排序的单调性要求为升序排序或降序排序，当升序排序时，各排序分段中的数据均按照升序排序，当降序排序时，各排序分段中的数据均按照
降序排序。由于升序排序或降序排序，对于同一序列组对应的任意两个排序分段，其中一个
排序分段的最大值小于另一个排序分段的最小值，因此可以直接按照单调性要求对各排序
分段进行排序，生成每一个序列组的归并排序结果。

[0093] 本发明实施例提供的归并排序方法首先获取待归并排序数据形成的有序序列的数量，并在有序序列的数量与CAS的数量是否满足预设条件的情况下对各有序序列进行分
段，获取各有序序列的数据分段，然后通过所述CAS对每一个序列组中的有序序列的数据分
段进行归并排序，获取每一个序列组对应的排序分段，最后按照归并排序的单调性要求，对
每一个序列组对应的各排序分段进行排序，生成每一个序列组的归并排序结果。由于本发
明实施例提供的归并排序方法可以在有序序列的数量与CAS的数量是否满足预设条件的情
况下对各有序序列进行分段，并通过所述CAS对每一个序列组中的有序序列的数据分段进
行归并排序，因此本发明实施例提供的归并排序方法可以在归并排序过程中减少处于空闲
状态的CAS的数量，提升硬件资源利用率，进而提升归并排序效率。

[0094] 本发明另一实施例提供了一种归并排序方法，参照图2所示，该归并排序方法，包括如下步骤：

[0095] S21、获取待归并排序数据形成的有序序列的数量。

[0096] S22、判断所述有序序列的数量与比较交换单元CAS的数量是否满足预设条件。

[0097] 在上述步骤S22中，若有序序列的数量与比较交换单元CAS的数量满足预设条件，则执行如下步骤S23。

[0098] S23、将每一个序列组中的第一有序序列均等的划分为N个第一数据分段。

[0099] 其中，N为大于1的整数。

[0100] S24、根据各第一数据分段的边界值，将各第一数据分段对应的第二有序序列划分为至少一个第二数据分段。

[0101] 其中，任一第一数据分段对应的第二有序序列为划分得到该第一数据分段的第一有序序列所属的序列组中的另一个有序序列。

[0102] 例如：序列组中包括有序序列A和有序序列B，若将有序序列A均等的划分为N个第一数据分段，则第一数据分段对应的第二有序序列为有序序列B，若将有序序列B均等的划
分为N个第一数据分段，则第一数据分段对应的第二有序序列为有序序列A。

[0103] 示例性的，以下以序列组AB(包括：有序序列A和有序序列B)为例对上述步骤S23以及S24进行举例说明。如图3所示，首先将有序序列A划分为第一数据分段a1和第一数据分段
a2，第一数据分段a1的最小值为mina1，第一数据分段a1的最大值为maxa1，第一数据分段a2
的最小值为mina2，第一数据分段a2的最大值为maxa2，且mina2>maxa1，则可以根据第一数据分
段a1的边界值和第一数据分段a2的边界值，将有序序列B分为4个第二数据分段，其中，第二
数据分段b1的最小值为有序序列B的最小值，第二数据分段b1的最大值maxb1为有序序列B的
mina1，第二数据分段b2的边界值与第一数据分段a1的边界值相同，第二数据分段b3的最小
值为maxa1，第二数据分段b3的最大值mina2，第二数据分段b4的边界值与第一数据分段a2的
边界值相同。

[0104] 需要说明的是，当第二有序序列中不包括第一数据分段的边界值时，无法得到与各第一数据分段边界值完全相同的第二数据分段，在这种情况下，只需要满足划分得到的
第二数据分段仅与一个第一数据分段具有交集，或与全部第一数据分段均无交集即可。例
如：图3所示示例中，可以取一个大于或等于maxa1且小于或等于mina2的值，将有序序列B划
分为两个第二数据分段。

[0105] S25、通过所述CAS对各第一数据分段和对应的第二数据分段进行归并排序，获取各数据分段的归并排序结果。

[0106] 其中，任一第一数据分段对应的第二数据分段为与该第一数据分段具有交集的第二数据分段。

[0107] 承图3所示示例所述，第一数据分段a1对应的第二数据分段为b2、第一数据分段a2对应的第二数据分段为b4，因此通过一个CAS对第一数据分段a1和第二数据分段b2进行归
并排序，通过一个CAS对第一数据分段a2和第二数据分段b4进行归并排序。

[0108] S26、按照归并排序的单调性要求，对每一个序列组对应的各排序分段进行排序，生成每一个序列组的归并排序结果。

[0109] 承上示例所述，设：第一数据分段a1和第二数据分段b2进行归并排序的排序分段为排序分段c，第一数据分段a2和第二数据分段b4进行归并排序的排序分段为d，则按照归
并排序的单调性要求，对每一个序列组对应的各排序分段进行排序，生成每一个序列组的
归并排序结果可以如图4所示，依次为第二数据分段b1、排序分段c、第二数据分段b3以及排
序分段d。

[0110] 本发明另一实施例提供了一种归并排序方法，参照图5所示，该归并排序方法，包括如下步骤：

[0111] S51、获取待归并排序数据形成的有序序列的数量。

[0112] S52、判断所述有序序列的数量与比较交换单元CAS的数量是否满足预设条件。

[0113] 在上述步骤S52中，若有序序列的数量与比较交换单元CAS的数量满足预设条件，则执行如下步骤S53。

[0114] S53、将每一个有序序列均等的划分为M个数据分段。

[0115] 其中，M为大于1的整数。

[0116] S54、确定属于同一序列组的第一有序序列和第二有序序列的各数据分段的覆盖范围的交集情况。

[0117] 具体的，本发明实施例中任一数据分段的覆盖范围是指该有序序列的最大值与该有序序列的最小值组成的数值范围。例如：某一数据分段为“7 10 18 24……68”，则该数据
分段的覆盖范围为[7，68]。

[0118] 在上述步骤S54中，若同一序列组中的第一有序序列和第二有序序列的各数据分段的覆盖范围的交集情况为第一情况(第一数据分段和第二数据分段分别为同一序列组中
的第一有序序列和第二有序序列的数据分段、所述第一数据分段的覆盖范围仅与所述第二
数据分段的覆盖范围具有交集，且所述第二数据分段的覆盖范围仅与所述第一数据分段的
覆盖范围具有交集)，则执行如下步骤S55。

[0119] S55、通过所述CAS对所述第一数据分段和所述第二数据分段进行归并排序。

[0120] 具体的，参照图6所示，图6中以椭圆和矩形分别形表示同一序列组中的第一有序序列的数据分段和第二有序序列的数据分段。所述第一数据分段的覆盖范围仅与所述第二
数据分段的覆盖范围具有交集，且所述第二数据分段的覆盖范围仅与所述第一数据分段的
覆盖范围具有交集，包括图6所示的4种情形：

[0121] 情形1：如图6中6a所示，a1为第一数据分段，b1、b2、b3为连续的三个第二数据分段，maxb1maxa1>maxb2，因此确定第一数据分段a1的覆盖范围仅与第二数
据分段b2的覆盖范围具有交集，且第二数据分段b2的覆盖范围仅与第一数据分段a1的覆盖
范围具有交集。

[0122] 情形2：如图6中6b所示，a1、a2、a3为连续的三个第一数据分段，b1为第二数据分段，若存在maxa1maxb1>maxa2，则确定第一数据分段a2的覆盖范围仅与第
二数据分段b1的覆盖范围具有交集，且第二数据分段b1的覆盖范围仅与第一数据分段a2的
覆盖范围具有交集。

[0123] 情形3：如图6中6c所示，a1、a2为连续的两个第一数据分段，b1、b2为连续的两个第二数据分段，maxa1maxa2>maxb1，因此确定第一数据分段a2的覆盖范围仅
与第二数据分段b1的覆盖范围具有交集，且第二数据分段b1的覆盖范围仅与第一数据分段
a2的覆盖范围具有交集。

[0124] 情形4：如图6中6d所示，a1、a2为连续的两个第一数据分段，b1、b2为连续的两个第二数据分段，maxb1maxb2>maxa1，因此确定第一数据分段a1的覆盖范围仅
与第二数据分段b2的覆盖范围具有交集，且第二数据分段b2的覆盖范围仅与第一数据分段
a1的覆盖范围具有交集。

[0125] 在上述步骤S54中，若同一序列组中的第一有序序列和第二有序序列的各数据分段的覆盖范围的交集情况为第二情况(第一数据分段和多个第二数据分段分别为同一序列
组中的第一有序序列和第二有序序列数据分段、所述第一数据分段的覆盖范围仅与所述多
个第二数据分段中的每一个第二数据分段的覆盖范围均有交集，且所述多个第二数据分段
中每一个第二数据分段的覆盖范围都均仅与所述第一数据分段的覆盖范围具有交集)，则
执行如下步骤S56和S57。

[0126] S56、拼接所述多个第二数据分段获取第三数据分段。

[0127] S57、通过所述CAS对所述第一数据分段和所述第三数据分段进行归并排序。

[0128] 具体的，参照图7所示，图7中以椭圆和矩形分别形表示同一序列组中的第一有序序列的数据分段和第二有序序列的数据分段。所述第一数据分段的覆盖范围仅与所述多个
第二数据分段中的每一个第二数据分段的覆盖范围均有交集，且所述多个第二数据分段中
每一个第二数据分段的覆盖范围都均仅与所述第一数据分段的覆盖范围具有交集，包括图
7所示的4种情形：

[0129] 情形1：如图7中7a所示，a1为第一数据分段，b1、b2、……、bn、bn+1为连续的多个第二数据分段，maxb1maxa1>maxbn，因此确定第一数据分段a1的覆盖范围
仅与第二数据分段b2至bn的覆盖范围具有交集，且第二数据分段b2至bn中每一个第二数据
分段的覆盖范围都仅与第一数据分段a1的覆盖范围具有交集，因此将第二数据分段b2至bn
合并为一个数据分段，并与第一数据分段a1进行归并排序。

[0130] 情形2：如图7中7b所示，a1、a2、a3为连续的三个第一数据分段，b1、b2、……、bn为连续的多个第二数据分段，maxa1maxbn>maxa2，因此确定第一数据分段a2
的覆盖范围仅与第二数据分段b1至bn的覆盖范围具有交集，且第二数据分段b1至bn的覆盖
范围仅与第一数据分段a2的覆盖范围具有交集，因此将第二数据分段b1至bn合并为一个数
据分段，并与第一数据分段a2进行归并排序。

[0131] 情形3：如图7中7c所示，a1、a2为连续的两个第一数据分段，b1、b2、……、bn、bn+1为连续的多个第二数据分段，maxa1maxa2>maxbn，因此确定第一数据分
段a2的覆盖范围仅与第二数据分段b1至bn的覆盖范围具有交集，且第二数据分段b1至bn的
覆盖范围仅与第一数据分段a2的覆盖范围具有交集，因此将第二数据分段b1至bn合并为一
个数据分段，并与第一数据分段a2进行归并排序。

[0132] 情形4：如图7中7d所示，a1、a2为连续的两个第一数据分段，b1、b2、……、bn为连续的多个第二数据分段，maxb1maxbn>maxa1，因此确定第一数据分段a1的覆
盖范围仅与第二数据分段b2至bn的覆盖范围具有交集，且第二数据分段b1至bn的覆盖范围
仅与第一数据分段a1的覆盖范围具有交集，因此将第二数据分段b2至bn合并为一个数据分
段，并与第一数据分段a1进行归并排序。

[0133] 在上述步骤S54中，同一序列组中的第一有序序列和第二有序序列的各数据分段的覆盖范围的交集情况为第三情况(第一数据分段和第二数据分段为目标序列组中的第一
有序序列的数据分段，第三数据分段和第四数据分段为目标序列组中的第二有序序列的数
据分段，所述第一数据分段的覆盖范围仅与所述第三数据分段的覆盖范围、所述第四数据
分段的覆盖范围均具有交集，且所述第二数据分段的覆盖范围仅与所述第四数据分段的覆
盖范围具有交集)，则执行如下步骤S58至S511。

[0134] S58、根据所述第一数据分段的边界值将所述第四数据分段划分为第五数据分段和第六数据分段。

[0135] S59、将所述第五数据分段和第六数据分段中覆盖范围与所述第一数据分段的覆盖范围具有交集的数据分段与所述第三数据分段拼接为第七数据分段。

[0136] S510、通过所述CAS对所述第一数据分段和所述第七数据分段进行归并排序。

[0137] S511、通过所述CAS对所述第二数据分段和所述第五数据分段和第六数据分段中覆盖范围与所述第二数据分段的覆盖范围具有交集的数据分段进行归并排序。

[0138] 具体的，参照图8所示，图8中以椭圆和矩形分别形表示同一序列组中的第一有序序列的数据分段和第二有序序列的数据分段。所述第一数据分段的覆盖范围仅与所述第三
数据分段的覆盖范围、所述第四数据分段的覆盖范围均具有交集，且所述第二数据分段的
覆盖范围仅与所述第四数据分段的覆盖范围具有交集的一种情形为：a1、a2、a3、a4为连续
的四个第一数据分段，b1、b2为连续的两个第二数据分段，maxa1maxa2均具有交集，且a3的覆盖范围仅与b2的覆盖范围具有交集，则将根据maxa2将b2划分为b21和
b22，然后再将b1与b21合并得到c，最后对c和a2进行归并排序，对b22和a3进行归并排序。

[0139] 在上述实施例的基础上，第一数据分段的覆盖范围仅与所述第三数据分段的覆盖范围、所述第四数据分段的覆盖范围均具有交集，且所述第二数据分段的覆盖范围仅与所
述第四数据分段的覆盖范围具有交集的情形还包括多种，本发明实施例在此不再一一枚
举，但都可以通过上述S58至S511提供的归并排序方式进行归并排序。

[0140] 在上述步骤S54中，若同一序列组中的第一有序序列和第二有序序列的各数据分段的覆盖范围的交集情况为第四情况(第一数据分段为目标序列组中的第一有序序列的数
据分段，第二数据分段和第三数据分段依次为目标序列组中的第二有序序列的连续的两个
数据分段，所述第一数据分段的覆盖范围位于所述第二数据分段的覆盖范围和所述第三数
据分段的覆盖范围之间)，则执行如下步骤S512。

[0141] S512、将第一数据分段拼接于所述第二数据分段之后或所述第三数据分段之前。

[0142] 具体的，参照图9所示，图9中以椭圆和矩形分别形表示同一序列组中的第一有序序列的数据分段和第二有序序列的数据分段。若第一数据分段为目标序列组中的第一有序
序列的数据分段，第二数据分段和第三数据分段依次为目标序列组中的第二有序序列的连
续的两个数据分段，所述第一数据分段的覆盖范围位于所述第二数据分段的覆盖范围和所
述第三数据分段的覆盖范围之间的一种情形为：a1为第一数据分段，b1、b2为连续的两个第
二数据分段，maxb1范围之间，因此将a1拼接于b1之后或b2之前。

[0143] S513、按照归并排序的单调性要求，对每一个序列组对应的各排序分段进行排序，生成每一个序列组的归并排序结果。

[0144] 基于同一发明构思，作为对上述方法的实现，本发明实施例还提供了一种归并排序装置，该归并排序装置实施例与前述方法实施例对应，为便于阅读，本装置实施例不再对
前述方法实施例中的细节内容进行逐一赘述，但应当明确，本实施例中的归并排序装置能
够对应实现前述方法实施例中的全部内容。

[0145] 图10为本发明实施例提供的归并排序装置的结构示意图，如图10所示，本实施例提供的归并排序装置100包括：

[0146] 获取单元101，用于获取待归并排序数据形成的有序序列的数量；

[0147] 处理单元102，用于判断所述有序序列的数量与比较交换单元CAS的数量是否满足预设条件；

[0148] 分段单元103，用于在所述有序序列的数量与比较交换单元CAS的数量满足预设条件的情况下，对各有序序列进行分段，获取各有序序列的数据分段；

[0149] 归并排序单元104，用于通过所述CAS对每一个序列组中的有序序列的数据分段进行归并排序，获取每一个序列组对应的排序分段，任一序列组包括待归并排序的两个有序
序列；

[0150] 生成单元105，用于按照归并排序的单调性要求，对每一个序列组对应的各排序分段进行排序，生成每一个序列组的归并排序结果。

[0151] 作为本发明实施例一种可选的实施方式，所述分段单元103，具体用于将每一个序列组中的第一有序序列均等的划分为N个第一数据分段，N为大于1的整数；

[0152] 根据各第一数据分段的边界值，将各第一数据分段对应的第二有序序列划分为至少一个第二数据分段；

[0153] 其中，任一第一数据分段对应的第二有序序列为划分得到该第一数据分段的第一有序序列所属的序列组中的另一个有序序列。

[0154] 作为本发明实施例一种可选的实施方式，所述归并排序单元104，具体用于通过所述CAS对各第一数据分段和对应的第二数据分段进行归并排序，获取各数据分段的归并排
序结果；

[0155] 其中，任一第一数据分段对应的第二数据分段为与该第一数据分段具有交集的第二数据分段。

[0156] 作为本发明实施例一种可选的实施方式，所述分段单元103，具体用于将每一个有序序列均等的划分为M个数据分段；

[0157] 其中，M为大于1的整数。

[0158] 作为本发明实施例一种可选的实施方式，所述归并排序单元104，具体用于若第一数据分段和第二数据分段分别为同一序列组中的第一有序序列和第二有序序列的数据分
段、所述第一数据分段的覆盖范围仅与所述第二数据分段的覆盖范围具有交集，且所述第
二数据分段的覆盖范围仅与所述第一数据分段的覆盖范围具有交集，则通过所述CAS对所
述第一数据分段和所述第二数据分段进行归并排序；

[0159] 若第一数据分段和多个第二数据分段分别为同一序列组中的第一有序序列和第二有序序列数据分段、所述第一数据分段的覆盖范围仅与所述多个第二数据分段中的每一
个第二数据分段的覆盖范围均有交集，且所述多个第二数据分段中每一个第二数据分段的
覆盖范围都均仅与所述第一数据分段的覆盖范围具有交集，则拼接所述多个第二数据分段
获取第三数据分段，并通过所述CAS对所述第一数据分段和所述第三数据分段进行归并排
序；

[0160] 若第一数据分段和第二数据分段为目标序列组中的第一有序序列的数据分段，第三数据分段和第四数据分段为目标序列组中的第二有序序列的数据分段，所述第一数据分
段的覆盖范围仅与所述第三数据分段的覆盖范围、所述第四数据分段的覆盖范围均具有交
集，且所述第二数据分段的覆盖范围仅与所述第四数据分段的覆盖范围具有交集，则根据
所述第一数据分段的边界值将所述第四数据分段划分为第五数据分段和第六数据分段，将
所述第五数据分段和第六数据分段中覆盖范围与所述第一数据分段的覆盖范围具有交集
的数据分段与所述第三数据分段拼接为第七数据分段，并通过所述CAS对所述第一数据分
段和所述第七数据分段进行归并排序，通过所述CAS对所述第二数据分段和所述第五数据
分段和第六数据分段中覆盖范围与所述第二数据分段的覆盖范围具有交集的数据分段进
行归并排序。

[0161] 作为本发明实施例一种可选的实施方式，所述处理单元102，具体用于判断所述有序序列的数量是否小于所述CAS的数量的两倍；若所述序序列的数量小于所述CAS的数量的
两倍，则确定所述有序序列的数量与所述CAS的数量满足预设条件；若所述序序列的数量大
于或等于所述CAS的数量的两倍，则确定所述有序序列的数量与所述CAS的数量不满足预设
条件。

[0162] 本实施例提供的归并排序装置可以执行上述方法实施例提供的归并排序方法，其实现原理与技术效果类似，此处不再赘述。

[0163] 基于同一发明构思，本发明实施例还提供了一种电子设备。图11为本发明实施例提供的电子设备的结构示意图，如图11所示，本实施例提供的电子设备包括：存储器111和
处理器112，存储器111用于存储计算机程序；处理器112用于在调用计算机程序时执行上述
方法实施例提供的归并排序方法中的各步骤。

[0164] 具体的，存储器111可用于存储软件程序以及各种数据。存储器111可主要包括存储程序区和存储数据区，其中，存储程序区可存储操作系统、至少一个功能所需的应用程序
(比如声音播放功能、图像播放功能等)等；存储数据区可存储根据手机的使用所创建的数
据(比如音频数据、电话本等)等。此外，存储器111可以包括高速随机存取存储器，还可以包
括非易失性存储器，例如至少一个磁盘存储器件、闪存器件、或其他易失性固态存储器件。

[0165] 处理器112是电子设备的控制中心，利用各种接口和线路连接整个电子设备的各部分，通过运行或执行存储在存储器111中的软件程序和/或模块，以及调用存储在存储器
111中的数据，执行电子设备的各种功能和处理数据，从而对电子设备进行整体监控。处理
器112可包括一个或多个处理单元。

[0166] 此外，应当理解的是，本发明实施例提供的电子设备还可以包括：射频单元、网络模块、音频输出单元、传感器、信号接收单元、显示器、用户接收单元、接口单元、以及电源等
部件。本领域技术人员可以理解，上述描述出的电子设备的结构并不构成对电子设备的限
定，电子设备可以包括更多或更少的部件，或者组合某些部件，或者不同的部件布置。在本
发明实施例中，电子设备包括但不限于手机、平板电脑、笔记本电脑、掌上电脑、车载终端、
可穿戴设备、以及计步器等。

[0167] 其中，射频单元可用于收发信息或通话过程中，信号的接收和发送，具体的，将来自基站的下行数据接收后，给处理器112处理；另外，将上行的数据发送给基站。通常，射频
单元包括但不限于天线、至少一个放大器、收发信机、耦合器、低噪声放大器、双工器等。此
外，射频单元还可以通过无线通信系统与网络和其他设备通信。

[0168] 电子设备通过网络模块为用户提供了无线的宽带互联网访问，如帮助用户收发电子邮件、浏览网页和访问流式媒体等。

[0169] 音频输出单元可以将射频单元或网络模块接收的或者在存储器111中存储的音频数据转换成音频信号并且输出为声音。而且，音频输出单元还可以提供与电子设备执行的
特定功能相关的音频输出(例如，呼叫信号接收声音、消息接收声音等等)。音频输出单元包
括扬声器、蜂鸣器以及受话器等。

[0170] 信号接收单元用于接收音频或视频信号。接收单元可以包括图形处理器(Graphics Processing Unit，GPU)和麦克风，图形处理器对在视频捕获模式或图像捕获模
式中由图像捕获装置(如摄像头)获得的静态图片或视频的图像数据进行处理。处理后的图
像帧可以显示在显示单元上。经图形处理器处理后的图像帧可以存储在存储器(或其它存
储介质)中或者经由射频单元或网络模块进行发送。麦克风可以接收声音，并且能够将这样
的声音处理为音频数据。处理后的音频数据可以在电话通话模式的情况下转换为可经由射
频单元发送到移动通信基站的格式输出。

[0171] 电子设备还包括至少一种传感器，比如光传感器、运动传感器以及其他传感器。具体地，光传感器包括环境光传感器及接近传感器，其中，环境光传感器可根据环境光线的明
暗来调节显示面板的亮度，接近传感器可在电子设备移动到耳边时，关闭显示面板和/或背
光。作为运动传感器的一种，加速计传感器可检测各方向上(一般为三轴)加速度的大小，静
止时可检测出重力的大小及方向，可用于识别电子设备姿态(比如横竖屏切换、相关游戏、
磁力计姿态校准)、振动识别相关功能(比如计步器、敲击)等；传感器还可以包括指纹传感
器、压力传感器、虹膜传感器、分子传感器、陀螺仪、气压计、湿度计、温度计、红外线传感器
等，在此不再赘述。

[0172] 显示单元用于显示由用户输入的信息或提供给用户的信息。显示单元可包括显示面板，可以采用液晶显示器(Liquid Crystal Display，LCD)、有机发光二极管(Organic 
Light‑Emitting Diode,OLED)等形式来配置显示面板。

[0173] 用户接收单元可用于接收输入的数字或字符信息，以及产生与电子设备的用户设置以及功能控制有关的键信号输入。具体地，用户接收单元包括触控面板以及其他输入设
备。触控面板，也称为触摸屏，可收集用户在其上或附近的触摸操作(比如用户使用手指、触
笔等任何适合的物体或附件在触控面板上或在触控面板附近的操作)。触控面板可包括触
摸检测装置和触摸控制器两个部分。其中，触摸检测装置检测用户的触摸方位，并检测触摸
操作带来的信号，将信号传送给触摸控制器；触摸控制器从触摸检测装置上接收触摸信息，
并将它转换成触点坐标，再送给处理器112，接收处理器112发来的命令并加以执行。此外，
可以采用电阻式、电容式、红外线以及表面声波等多种类型实现触控面板。除了触控面板，
用户接收单元还可以包括其他输入设备。具体地，其他输入设备可以包括但不限于物理键
盘、功能键(比如音量控制按键、开关按键等)、轨迹球、鼠标、操作杆，在此不再赘述。

[0174] 进一步的，触控面板可覆盖在显示面板上，当触控面板检测到在其上或附近的触摸操作后，传送给处理器112以确定触摸事件的类型，随后处理器112根据触摸事件的类型
在显示面板上提供相应的视觉输出。一般情况下，触控面板与显示面板是作为两个独立的
部件来实现电子设备的输入和输出功能，但是在某些实施例中，可以将触控面板与显示面
板集成而实现电子设备的输入和输出功能，具体此处不做限定。

[0175] 接口单元为外部装置与电子设备连接的接口。例如，外部装置可以包括有线或无线头戴式耳机端口、外部电源(或电池充电器)端口、有线或无线数据端口、存储卡端口、用
于连接具有识别模块的装置的端口、音频输入/输出(I/O)端口、视频I/O端口、耳机端口等
等。接口单元可以用于接收来自外部装置的输入(例如，数据信息、电力等等)并且将接收到
的输入传输到电子设备中的一个或多个元件或者可以用于在电子设备和外部装置之间传
输数据。

[0176] 电子设备还可以包括给各部件供电的电源(比如电池)，可选的，电源可以通过电源管理系统与处理器112逻辑相连，从而通过电源管理系统实现管理充电、放电、以及功耗
管理等功能。

[0177] 本发明实施例还提供一种计算机可读存储介质，该计算机可读存储介质上存储有计算机程序，计算机程序被处理器执行时实现上述方法实施例提供的归并排序方法。

[0178] 本领域技术人员应明白，本发明的实施例可提供为方法、系统、或计算机程序产品。因此，本发明可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施
例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可
用存储介质上实施的计算机程序产品的形式。

[0179] 计算机可读介质包括永久性和非永久性、可移动和非可移动存储介质。存储介质可以由任何方法或技术来实现信息存储，信息可以是计算机可读指令、数据结构、程序的模
块或其他数据。计算机的存储介质的例子包括，但不限于相变内存(PRAM)、静态随机存取存
储器(SRAM)、动态随机存取存储器(DRAM)、其他类型的随机存取存储器(RAM)、只读存储器
(ROM)、电可擦除可编程只读存储器(EEPROM)、快闪记忆体或其他内存技术、只读光盘只读
存储器(CD‑ROM)、数字多功能光盘(DVD)或其他光学存储、磁盒式磁带，磁盘存储或其他磁
性存储设备或任何其他非传输介质，可用于存储可以被计算设备访问的信息。根据本文中
的界定，计算机可读介质不包括暂存电脑可读媒体(transitorymedia)，如调制的数据信号
和载波。

[0180] 需要说明的是，在本文中，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而
且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有
的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所
述要素的过程、方法、物品或者设备中还存在另外的相同要素。

[0181] 以上所述仅是本发明的具体实施方式，使本领域技术人员能够理解或实现本发明。对这些实施例的多种修改对本领域的技术人员来说将是显而易见的，本文中所定义的
一般原理可以在不脱离本发明的精神或范围的情况下，在其它实施例中实现。因此，本发明
将不会被限制于本文所述的这些实施例，而是要符合与本文所公开的原理和新颖特点相一
致的最宽的范围。