对电子表格中的数据项的多线程排序

摘要

为对电子表格中的数据项进行排序，将该电子表格中的数据项分成多个块。使用多个线程来对各块中的数据项进行排序。在块中的数据项被排序之后，使用多个合并线程来生成最终结果块。最终结果块包含电子表格中的每一个数据项。每一个合并线程都是合并两个源块以生成结果块的线程。每一个源块是一个经排序块或由另一合并线程生成的一个结果块。然后，显示电子表格的经排序版本。电子表格的经排序版本中的数据项是根据最终结果块中的数据项的次序来排序的。

说明书

背景

电子表格应用使用户能够查看和操纵表格数据。例如，电子表格应用可使 用户能够查看和操纵包含对应于不同产品的各行以及对应于不同仓库的各列 的电子表格。在该示例中，单元格包含指示各仓库处的产品库存的值。在许多 情况下，用户想要能够对电子表格中的各行进行排序。继续上述示例，用户可 能想要基于一特定仓库包含每一产品的量来对电子表格中的各行进行排序。在 其他情况下，用户想要能够对电子表格中的各列进行排序。继续上述示例，用 户可能想要基于一特定产品在每一仓库中的量来对电子表格中的各列进行排 序。

在大型电子表格中，对电子表格中的各行进行排序的过程可能是相当缓慢 的。这一处理延迟可能中断用户的思路或阻碍用户对电子表格中的各行进行排 序。因此，使对电子表格中的各行进行排序的过程尽可能快是合乎需要的。

概述

对电子表格执行排序过程。在排序过程中，电子表格中的数据项被分成多 个块。使用多个线程来对各块中的数据项进行排序。在各块中的数据项被排序 之后，使用多个合并线程来生成最终结果块。最终结果块包含电子表格中的每 一个数据项。每一个合并线程是合并两个源块以生成结果块的线程。每一个源 块是一个经排序块或由另一个合并线程生成的一个结果块。然后，显示电子表 格的经排序版本。电子表格的经排序版本中的数据项是根据最终结果块中的数 据项的次序来排序的。

提供本概述以介绍一些概念。这些概念在以下详细描述中进一步描述。本 概述并不旨在标识所要求保护的主题的关键特征或必要特征，也不旨在用于帮 助确定所要求保护的主题的范围。

附图简述

图1是示出示例计算系统的框图。

图2是示出计算系统的示例替换实施例的框图。

图3是示出对电子表格进行排序的示例操作的流程图。

图4是示出示例线程树的图。

图5是示出在排序过程的合并阶段由叶线程执行的示例操作的流程图。

图6是示出由不完整的内部线程执行的示例操作的流程图。

图7是示出了由完整的内部线程执行的示例操作的流程图。

图8是示出了在排序过程的合并阶段由存储器管理线程执行的示例操作 的流程图。

图9是示出示例计算设备的框图。

详细描述

图1是示出示例计算系统100的框图。计算系统100是包括一个或多个计 算设备的系统。如本文所使用的，计算设备是处理信息的物理、有形设备。在 各实施例中，计算系统100包括各种类型的计算设备。例如，计算系统100可 包括一个或多个台式计算机、膝上型计算机、上网本计算机、手持式计算设备、 智能电话、独立服务器设备、刀片服务器设备、大型计算机、超级计算机和/ 或其他类型的计算设备。在其中计算系统100包括不止一个计算设备的实施例 中，计算系统100中的计算设备可以分布在各个位置并经由诸如因特网或局域 网等网络来进行通信。

如图1的示例所示，计算系统100包括数据存储系统102、处理系统104 和显示系统106。应当理解，在其他实施例中，计算系统100包括比图1的示 例所示更多或更少的组件。此外，应当理解，图1以简化形式示出了计算系统 100以便于理解。

数据存储系统102是包括一个或多个计算机可读数据存储介质的系统。计 算机可读数据存储介质是能够以易失性或非易失性方式存储数据的物理设备 或制品。在一些实施例中，数据存储系统102包括一个或多个非瞬时计算机可 读数据存储介质。计算机可读数据存储介质的示例类型包括随机存取存储器 （RAM）、只读存储器（ROM）、光盘（例如，CD-ROM、DVD、蓝光盘、 HDDVD盘等）、磁盘（例如，硬盘驱动器、软盘等）、固态存储器设备（例 如，闪存驱动器）、EEPROM、现场可编程门阵列（FPGA）等。在其中数据 存储系统102包括不止一个计算机可读数据存储介质的一些实施例中，计算机 可读数据存储介质分布在各个地理位置。

数据存储系统102存储表示电子表格应用108的计算机可读指令。在其中 数据存储系统102包括不止一个计算机可读数据存储介质的一些实施例中，表 示电子表格应用108的计算机可读指令分布在这些计算机可读数据存储介质中 的两个或更多个上。在其中数据存储系统102包括不止一个计算机可读数据存 储介质的其他实施例中，表示电子表格应用108的计算机可读指令只被存储在 这些计算机可读数据存储介质中的一个上。

处理系统104是包括多个处理单元110A到110N（统称为“处理单元110”） 的系统。在各实施例中，处理系统104包括各种数量的处理单元。例如，处理 系统104可包括一个、两个、四个、八个、十六个、三十二个、六十四个或其 他数量的处理单元。每一个处理单元110都是物理集成电路。每一个处理单元 110能够与其他处理单元110异步地执行计算机可读指令。结果，处理单元110 能够彼此并行地独立执行计算机可读指令。在一些实施例中，一个或多个处理 单元110可单独提供两个或更多逻辑处理单元。计算机可读指令可以在逻辑处 理单元上独立操作并且能够以其他方式像真实处理单元那样操作。

显示系统106是处理系统104用来向用户显示信息的系统。在各实施例中， 显示系统106以各种方式向用户显示信息。例如，在一些实施例中，显示系统 106包括图形界面和监视器。

处理系统104中的处理单元110执行表示电子数据表应用108的计算机可 读指令。表示电子数据表应用108的计算机可读指令在被处理单元110执行时 使得计算系统100提供电子数据表应用108。电子表格应用108使用户能够查 看和操纵一个或多个电子表格。电子表格是被组织为具有一行或多行以及一列 或多列的表格的数据。电子数据表表格可包含各种类型的数据。例如，表格数 据可以是销售数据、库存数据、军事数据、记账数据、统计数据、人口数据、 人口统计数据、财务数据、医学数据、体育数据、科学数据或可被呈现在表格 中的任何其他类型的可排序数据。

电子表格中的单元格可包含具有各种数据类型的值。例如，单元格中的值 可以是整数、实数、浮点数、字母数字文本串、日期、货币金额、布尔值等。 除了单元格中的值之外，每一个单元格还可具有各种其他属性。例如，每一个 单元格都可具有背景颜色属性、字体颜色属性、一个或多个标志属性、可见性 属性、字体样式属性、字体大小属性等。

电子表格应用108能够使用多个线程来对电子表格执行排序过程。线程是 程序的一部分，该部分能够独立于该程序中的其他部分且与其他部分并发地运 行。该排序过程可以对电子表格中的各行或各列执行。为了解释方便，本文讨 论对电子表格中的各行执行排序操作。然而，应当理解，除非另外指明，否则 本文中的对行的讨论可以等同地适用于列。术语“数据项”在本文中用来大致 指代一行或一列。

排序过程对电子表格中的各行进行排序。在各种情况下，电子表格可以是 完整的电子表格、表格的一部分或另一种类型的电子表格。此外，在一些实施 例中，电子表格应用108的用户选择电子表格。

此外，在一些实施例中，电子表格可以是数据透视表。数据透视表是汇总 一个或多个其他表格数据集的电子表格，其他数据集是诸如电子表格、关系数 据库表、在线分析处理（OLAP）数据立方体、其他类型的多维数据集和其他 类型的表格数据集。在某些实施例中，用户能够通过选择源表中的行标签列和 列标签列来创建数据透视表。行标签列中的单元格中的值变为数据透视表的行 标签。列标签列中的单元格中的值变为数据透视表的列标签。每一数据透视表 单元格中的值都是根据列标签列中的与包含该数据透视表单元格的数据透视 表行的行标签具有相同值的单元格的值来计算出的。数据透视表也可以包括具 有根据数据透视表的单元格中的值计算出的值的单元格。例如，数据透视表可 包括包含数据透视表的列或行中的值的总计或计数的单元格。在某些实施例 中，用户还能够通过选择源表的行而并非源表的列来创建数据透视表。

在某些实施例中，用户能够选择两个或更多行标签列和列标签列。在这样 的实施例中，行标签列的单元格中的值的组合变为数据透视表中的行的行标 签，而列标签列中的单元格的值变为数据透视表中的列标签。

在一些实施例中，电子表格可包括隐藏行。隐藏行是在电子表格中但对电 子表格应用108的用户不可见的行。用户可选择隐藏特定行以简化电子表格的 外观。在这些实施例中，排序过程对电子表格中的隐藏行和可见行进行排序。

对电子表格中的各行进行排序包括操纵电子表格中的各行的次序以使得 电子表格中的各行被适当地排序。当电子表格中的各行针对每一个排序依据 （sort-by）列被适当地排序时，这些行被适当地排序。排序依据列是作为电子 表格中的各行的排序依据的列。在对各列的排序操作中，当电子表格中的各列 针对每一排序依据行被适当地排序时，这些列被适当地排序。术语“排序依据 线”在本文中用来大致指代排序依据列或排序依据行。

每一排序依据列都具有排序要求。排序要求包括相关属性和排序关系。相 关属性可以是排序依据列中的单元格的各种不同属性。例如，相关属性可以是 单元格中的值、单元格的颜色、单元格上的标志、单元格中的字体颜色、单元 格中的字体样式、单元格中的字体大小、单元格的隐藏/可见状态以及单元格的 其他属性。

排序关系是定义如何对属性进行排序的一个或多个规则的集合。排序关系 的示例类型包括字母排序、逆字母排序、数字排序、逆数字排序、年代排序、 逆年代排序、类别排序、地理排序和其它类型的排序。作为类别排序的一个特 定示例，排序关系可通过指示所有真值在任何假值前面来定义布尔值排序。在 另一示例中，排序关系可通过指示蓝色单元格在绿色单元格前面、黄色单元格 在蓝色单元格前面、红色单元格在黄色单元格前面等来定义单元格颜色排序。 在一些实施例中，电子表格应用108的用户能够选择排序依据列和排序依据列 的排序要求。

当存在多个排序依据列时，对排序依据列进行排名。电子表格中的各行首 先根据排名最高的排序依据列的排序要求来进行排序，然后根据排名第二高的 排序依据列的排序要求来进行排序，以此类推。因此，各行在以下情况下针对 给定排序依据列被适当地排序：对于在每一个排名较高的排序依据列的单元格 中具有相同的相关属性的任意两行，这两行满足给定排序依据列的排序要求。 当给定排序依据列的排序关系对这两个单元格的相关属性保持为真时，这两行 满足给定排序依据列的排序要求。

如在本文中的其他地方详细描述的，电子表格应用108将电子表格中的各 行分成多个块。块是行的集合。因此，块可被认为是较小的电子表格。在一些 实施例中，每一块中的行数基于电子表格中的行数和处理单元110的数量。大 多数情况下，块的数量等于处理系统104中的处理单元110的数量。

在这些行被分成各块之后，排序过程进入块排序阶段。在块排序阶段期间， 电子表格应用108使用多个块排序线程来对各块中的各行进行排序。块排序线 程的数量等于块的数量。每一个块排序线程都用于对每一块中的各行进行排 序。

在块排序线程对各块中的各行进行排序之后，排序过程进入合并阶段。在 合并阶段期间，电子表格应用108使用多个合并线程来生成最终结果块。最终 结果块包含电子表格中的每一个行。最终结果块中的各行被适当地排序。每一 个合并线程都是合并两个源块以生成结果块的线程。合并线程的每一个源块可 以是块排序线程生成的经排序块或另一合并线程生成的结果块。例如，合并线 程的两个源块可以是块排序线程生成的经排序块。在另一示例中，合并线程的 源块可以是一个块排序线程生成的经排序块和另一合并线程生成的结果块。在 又一示例中，合并线程的两个源块可以是其他合并线程生成的结果块。

在生成最终结果块之后，电子表格应用108输出结果数据以便呈现给电子 表格应用108的用户。结果数据取决于最终结果块中的各行的次序。

在各实施例中，电子表格应用108输出各种类型的结果数据。例如，在一 些实施例中，电子表格应用108显示电子表格的经排序版本，其中该电子表格 中的各行根据最终结果块中的各行的次序来排序。此外，在一些实施例中，电 子表格应用108生成并显示示出最终结果块中的至少某些行的报告。此外，在 一些实施例中，结果数据不一定包括电子表格中的所有行。在结果数据由另一 进程来消费或者电子表格的子集将进行进一步排序的情况下，结果数据不一定 被呈现给用户。

图2是计算系统系统100的示例替换实施例的框图。如图2的示例所示， 计算系统100包括数据存储系统102和处理系统104，如同图1所示的示例实 施例。然而，不同于图1所示的示例实施例，图2所示的计算系统100的示例 替换实施例具有网络接口200而不是显示系统106。

网络接口系统200使得计算系统100能够经由网络204向客户机设备202 发送数据以及从客户机设备202接收数据。网络204是包括计算设备和方便在 计算系统100与客户机设备202之间进行通信的链接的通信网络。在各实施例 中，网络204包括各种类型的计算设备。例如，网络204可包括路由器、交换 机、移动接入点、网桥、集线器、侵入检测设备、存储设备、独立服务器设备、 刀片服务器设备、传感器、台式计算机、防火墙设备、膝上型计算机、手持式 计算机、移动电话和其他类型的计算设备。在各实施例中，网络204包括各种 类型的链接。例如，网络204可包括有线和/或无线链接。此外，在各实施例中， 网络204按各种规模实现。例如，网络204可被实现为一个或多个局域网 （LAN）、城域网、子网、广域网（诸如因特网）或可以按另一规模来实现。

客户机设备202是计算设备。例如，客户机设备202可以是用户使用的个 人计算机。用户使用客户机设备202来经由网络204向计算系统100发送请求 并从计算系统100接收信息。以此方式，用户可使用客户机设备202来采用电 子表格应用108来查看和操纵表格数据。例如，计算系统100可经由网络204 向客户机设备202发送结果数据。在该示例中，客户机设备202被配置成处理 结果数据以便向客户机设备202的用户显示电子表格的经排序版本。例如，客 户机设备202可呈现包含结果数据的网页或与客户机应用交互以显示结果数 据。

图3是示出对电子表格进行排序的示例操作300的流程图。如图3的示例 所示，操作300在电子表格应用108接收到排序命令（302）时开始。排序命 令指示电子表格应用108对特定电子表格启动排序过程。此外，排序命令可指 定相关属性、电子表格中的排序依据列和排序关系。在一些实施例中，电子表 格应用108的用户可选择电子表格、相关属性、排序依据列和/或排序关系。

在各实施例中，电子表格应用108以各种方式接收排序命令。例如，在一 些实施例中，电子表格应用108在该电子表格应用的用户选择电子表格应用 108的特定用户界面控件时接收到排序命令。此外，在一些实施例中，电子表 格应用108在用户输入特定键盘命令时接收到排序命令。此外，在一些实施例 中，电子表格应用108从在计算系统100、客户机设备202或另一计算设备上 操作的另一进程、线程或应用处接收排序命令。

此外，在一些实施例中，电子表格应用108在未从用户或另一进程、线程 或应用接收到显式排序命令的情况下开始操作300。例如，在一些实施例中， 电子表格应用108可定期或基于调度来自动开始操作300。此外，在一些实施 例中，电子表格应用108可以在用户更新电子表格中的一行或多行时自动开始 操作300。此外，在一些实施例中，电子表格应用108响应于检测到或接收到 指示从中绘制电子表格的数据源中发生了改变的事件而自动开始操作300。

响应于接收到排序命令或以其他方式接收到对电子表格启动排序过程的 指示，电子表格应用108确定电子表格中的总行数是否超过下限（304）。在 各实施例中，下限具有各种值。例如，在一些实施例中，下限是255。在其他 实施例中，下限大于255或小于255。在一些实施例中，电子表格应用108呈 现允许管理用户设置下限的用户界面。管理用户可以是接收结果数据的用户或 另一用户。

如果电子表格中的行数未超过下限（304为“否”），则电子表格应用 108使用单个线程来生成最终结果块（306）。该单个线程通过对电子表格中的 各行进行排序以使得该电子表格中的各行被适当地排序来生成最终结果块。当 电子表格中的行数相对较少时，使用单个线程来对各行进行排序可以比使用多 个线程来对各行进行排序更高效。这是因为可能存在与启动或唤醒线程相关联 的计算惩罚（例如，延迟）。这些计算惩罚可能只在存在足够数量的行时才是 值得遭受的。

如果电子表格中的行数超过下限（304为“是”），则电子表格应用108 确定适当的块数（308）。在各实施例中，电子表格应用108以各种方式确定 适当的块数。例如，在一些实施例中，最小作业大小是值得启动附加块排序线 程所需的块中的最少行数。在某些情况下，下限等于最小作业大小乘以2。在 此示例中，如果电子表格中的行数除以最小作业大小小于或等于处理系统104 中的处理单元110的数量，则适当的块数等于行数除以最小作业大小，向下舍 入。例如，如果有300行，最小作业大小是128，而处理系统104中有八个处 理单元，则适当的块数是2。如果电子表格中的行数除以最小作业大小大于或 等于处理系统104中的处理单元110的数量，则适当的块数等于处理单元110 的数量。例如，如果有30,000行，最小作业大小是128，而处理系统104中有 八个处理单元，则适当的块数是8。在某些实施例中，电子表格应用108呈现 可允许管理用户设置最小作业大小的用户界面。

接着，电子表格应用108将电子表格中的各行分成一组块（310）。该组 块中的块数等于适当的块数。该组块中的每一块都包含大致相同的行数。

在各实施例中，块以各种方式实现。例如，在一些实施例中，块被实现为 包含各行的标识符（例如，行“513”、行“234”、行“876”等）的数据结 构。在这些实施例中，将行插入块包括将行的标识符插入块并且对块中的各行 进行排序包括重新排列块中的各行的标识符。在其他实施例中，块是包括各行 的副本的数据结构。

在将各行分成各块后，电子表格应用108开始排序过程的块排序阶段。在 排序过程中的块排序阶段期间，电子表格应用108使用多个块排序线程来对各 块中的各行进行排序（312）。The number of block sorting threads in the set of block sorting threads is equal to the number of blocks in the set of blocks.For example,if the number of blocks is eight,the number of block sorting threads is eight.在某些情况下，每一个块排序线程在处理系统104中的不同的处理单元 110上并行执行。电子表格应用108向每一个块排序线程分配一个块。块排序 线程对分配给块排序线程的块中的行进行排序。在各实施例中，块排序线程使 用各种算法来对块中的行进行排序。例如，在各实施例中，块排序线程使用快 速排序算法（例如，qsort）、气泡排序算法、合并排序算法，或另一种排序算 法来对块中的行进行排序。

在电子表格应用108唤醒块排序线程组之后的某个时间，电子表格应用 108确定块排序线程已经完成了对每一个块的排序（314）。在各实施例中，电 子表格应用108以各种方式来确定块排序线程已经完成了对每一个块的排序。 例如，在某些实施例中，当块排序线程完成对块的排序时，块排序线程向电子 表格应用108提供完成指示。在其他实施例中，块排序线程将经排序块存储在 缓冲器中。在这样的实施例中，当缓冲器包含每一个块的经排序版本时，电子 表格应用108确定块排序线程已经完成了对块的排序。

在块排序线程完成对各块的排序之后，排序过程中的块排序阶段结束并且 排序过程中的合并阶段开始。在排序过程的合并阶段，电子表格应用108生成 线程树（316）。线程树是其中每一层（也许最后一层除外）都被完全填充的 二叉树。二叉树是其中每一个节点最多具有两个子节点的树形数据结构。

线程树中的合并线程的数量等于块的数量减去1。叶线程是在线程树中没 有子线程的合并线程。内部线程是在线程树中具有一个或多个子线程的合并线 程。不完整的内部线程是在线程树中只有一个子线程的内部线程。完整的内部 线程是在线程树中具有两个子线程的内部线程。根线程是在线程树中没有父线 程的合并线程。

如在本文中别处所描述的，叶线程用于合并分配给叶线程的经排序块，从 而生成结果块。结果块包含所分配的块中的每一行。结果块中的行被适当地排 序。不完整的内部线程用于将由其单个子线程生成的结果块与分配给不完整的 内部线程的经排序块合并。完整的内部线程用于将由其子线程生成的结果块合 并到更大的结果块中。最终，根线程生成最终结果块。

在各实施例中，电子表格应用108执行各种动作以生成线程树。例如，在 某些实施例中，电子表格应用108通过首先标识可用的合并线程和/或实例化合 并线程来生成线程树。在此示例中，电子表格应用108然后生成包含每一个合 并线程的项的指针数据结构。合并线程的项指定源指针和目的地指针。源指针 指定包含合并线程将要合并的块的存储器位置。目的地指针指定合并线程将要 把由合并线程所生成的结果块存储到那里的存储器位置。指针数据结构可以是 各种不同的类型的数据结构，包括数组、链表、矢量、表等等。

在生成线程树之后或作为生成线程树的过程的一部分，电子表格应用108 将两个块分配到线程树中的每一叶线程（318）。在各实施例中，电子表格应 用108以各种方式将块分配到叶线程。例如，在使用上文所描述的指针数据结 构的各实施例中，电子表格应用108通过在叶线程的项中提供指向块的存储器 位置的源指针来将块分配到叶线程。在另一示例中，电子表格应用108通过将 块的标识符作为参数提供到叶线程，来将块分配到叶线程。

此外，电子表格应用108还确定是否有奇数数量的块（320）。如果有奇 数数量的块，则线程树包含不完整的内部线程。因此，如果有奇数数量的块（320 为“是”），则电子表格应用108将其中一个块分配到不完整的内部线程（322）。

在将块分配到不完整的内部线程或确定没有奇数数量的块之后（320为 “否”），电子表格应用108使用合并线程来生成最终结果块（324）。为使 用合并线程来生成最终结果块，电子表格应用108唤醒合并线程。在各实施例 中，电子表格应用108以各种方式来唤醒合并线程。例如，在某些实施例中， 电子表格应用108通过向合并线程提供唤醒事件来唤醒合并线程。在其他实施 例中，电子表格应用108调用操作系统接口的一个或多个方法来唤醒合并线程。

随后，电子表格应用108从线程树中的根线程接收完成指示（326）。完 成指示指示根线程已经完成了最终结果块的生成。最终结果块包含电子表格中 的每一行。最终结果块中的行被适当地排序。

在电子表格应用108从根线程接收到完成指示之后，或者在行在步骤306 中被排序之后，电子表格应用108返回最终结果块（328）。随后，电子表格 应用108可以呈现取决于最终结果块的结果数据。

图4是示出了示例线程树400的图。如图4的示例所示，线程树400包括 线程402、线程404、线程407、线程408、线程410，以及线程412。线程402、 线程404，以及线程406是内部线程。线程402和线程404是完整的内部线程。 线程406是不完整的内部线程。线程408、线程410，以及线程412是叶线程。

此外，图4的示例还示出了块414和416被分配给线程408，块418和420 被分配给线程410，块422和424被分配给线程412，块426被分配给线程406。 换言之，块418和420是线程408的源块。块418和420是线程410的源块。 块422和424是线程412的源块。块426是线程406的源块。

线程408合并块414和416以生成结果块。线程410合并块418和420 以生成结果块。线程412合并块422和424以生成结果块。线程404合并由线 程408和410生成的结果块以生成结果块。换言之，由线程408和410生成的 结果块是线程404的源块。线程406合并由426和由线程412生成的结果块以 生成结果块。换言之，由线程412生成的结果块是线程406的源块。线程402 合并由线程404和406生成的结果块以生成最终结果块。换言之，由线程408 和406生成的结果块是线程402的源块。

图5是示出了在排序过程的合并阶段由叶线程所执行的示例操作500的流 程图。虽然是利用单个叶线程来说明操作500的，但是，线程树中的每一叶线 程都可以执行操作500。如图5的示例所示，当叶线程被电子表格应用108唤 醒时（502）操作500开始。唤醒线程是使线程准备运行的过程。在各实施例 中，电子表格应用108以各种方式来唤醒叶线程。例如，在某些实施例中，电 子表格应用108维护对能够执行操作500的休眠的线程的引用。在某些实施例 中，休眠的线程可包括在排序过程的块排序阶段所使用的块排序线程。换言之， 块排序线程中的一个可以充当叶线程。为唤醒叶线程，电子表格应用108向可 以执行操作500的线程提供唤醒事件，并给叶线程提供对分配给叶线程的第一 块和分配给叶线程的第二块的引用。

在叶线程唤醒之后，叶线程确定第一块中的最大行是否小于第二块中的最 小行（504）。由于第一块中的行被适当地排序，因此，第一块中的最大行是 第一块中的最后一行。由于第二块中的行被适当地排序，因此，第二块中的最 小行是第二块中的第一行。如果叶线程确定第一块中的最大行小于第二块中的 最小行，则在第一块和第二块之间没有重叠，没有必要比较第一块和第二块中 的单个行。相反地，如果叶线程确定第一块中的最大行小于第二块中的最小行 （504为“是”），则叶线程将第一块插入到结果块的小端处，并将第二块插 入到结果块的大端处（506）。以此方式，结果块包含第一块和第二块中的所 有行，结果块中的行被适当地排序。

如果叶线程确定第一块中的最大行不小于第二块中的最小行，则叶线程确 定第二块中的最大行是否小于第一块中的最小行（508）。由于第二块中的行 被适当地排序，因此，第二块中的最大行是第二块中的最后一行。由于第一块 中的行被适当地排序，因此，第一块中的最小行是第一块中的第一行。如果叶 线程确定第二块中的最大行小于第一块中的最小行（508为“是”），则叶线 程将第二块插入到结果块的小端处，并将第一块插入到结果块的大端处（510）。 以此方式，结果块包含第一块和第二块中的所有行，结果块中的行被适当地排 序。

如果第一块中的最大行大于第二块中的最小行，并且第二块中的最大行大 于第一块中的最小行，则在第一块和第二块之间有某种重叠。如果叶线程确定 第二块中的最大行不小于第一块中的最小行（508为“否”），则叶线程确定 在第一块中是否有任何剩余行（512）。当行还没有在结果块中时，该行是剩 余行。

如果在第一块中有一个或多个剩余行（512为“是”），则叶线程确定在 第二块中是否有任何剩余行（516）。如果在第二块中没有剩余行，则叶线程 已经将第二块中的所有行都插入到结果块中。因此，如果在第二块中没有剩余 行（516为“否”），则叶线程将第一块中的任何剩余行都插入到结果块中的 最大行之后（518）。在将第一块中的剩余行都插入到结果块中之后，结果块 包含第一块和第二块中的所有行，结果块中的行被适当地排序。

如果在第二块中有一个或多个剩余行（516为“是”），则叶线程标识最 小行（520）。最小行是第一块和第二块中的剩余行中的最小的。

如上所述，在一些实施例中，可选择多个排序依据列。例如，用户可指示 电子表格应首先根据“城市”列来排序，然后根据“日期”列来排序。如果存 在多个排序依据列并且如果两行的排名最高的排序依据列中的单元格中的相 关属性是相同的，则最小合并线程通过比较这两行的排名次高的排序依据列中 的单元格中的相关属性来标识最小行。如果排名次高的排序依据列中的单元格 的相关属性是相同的，则最小合并线程通过比较这两行的排名第三高的排序依 据列的单元格中的相关属性来标识最小行。该比较过程继续直到不再有排序依 据列或直到最小合并线程将一行标识为比另一行小。如果两行的所有排序依据 列中的单元格的相关属性是等同的，则最小合并线程可将任一行标识为最小 行。

叶线程将最小行插入到结果块中的最大行之后（522）。在将最小行插入 到结果块中之后，叶线程再次确定在第一块中是否有任何剩余行（512），依 次类推。

如果在第一块中没有剩余行，则叶线程已经将第一块中的所有行都插入到 结果块中。因此，如果在第一块中没有剩余行（512为“否”），则叶线程将 第二块中的任何剩余行都插入到结果块中的最大行之后（514）。在将第二块 中的剩余行都插入到结果块中之后，结果块包含第一块和第二块中的所有行， 结果块中的行被适当地排序。

在执行步骤506、510、518或522中的任何一个步骤之后，叶线程确定叶 线程是否是根线程（524）。如果叶线程是根线程（524为“是”），则叶线程 向电子表格应用108提供完成指示（526）。完成指示指示叶线程已经完成了 对第一块和第二块的合并。如果叶线程不是根线程（524为“否”），则叶线 程向叶线程的父线程提供完成指示（528）。在向电子表格应用或者叶线程的 父线程提供完成指示之后，叶线程休眠（530）。

图6是示出了由不完整的内部线程执行的示例操作600的流程图。当不完 整的内部线程被电子表格应用108唤醒时（602）操作600开始。电子表格应 用108向不完整的内部线程提供对第一块和第二块的引用。第一块是由不完整 的内部线程的子线程所生成的结果块。第二块是由块排序线程中的一个在排序 过程的块排序阶段所产生的块。不完整的内部线程和子线程在处理单元110的 不同的处理单元110上并行地操作。因此，当不完整的内部线程执行操作600 时，子线程生成第一块。结果，可能会有在第一块中没有剩余行，但是子线程 以后会将更多行插入到第一块中的情况。

在被唤醒之后，不完整的内部线程确定在第一块中是否有任何剩余行 （604）。如果在第一块中有一个或多个剩余行（604为“是”），则不完整的 内部线程确定在第二块中是否有任何剩余行（606）。

如果在第二块中没有剩余行（606为“否”），则不完整的内部线程将第 一块中的任何剩余行都插入到结果块中的最大行之后（608）。由于当不完整 的内部线程执行操作600时子线程生成第一块，因此，当不完整的内部线程正 在执行操作600时可以将行添加到第一块中。不完整的内部线程不确信，在子 线程向不完整的内部线程提供完成指示以前子线程将不会向第一块中添加到 任何额外的行。因此，在不完整的内部线程将第一块中的剩余行插入到结果块 中之后，不完整的内部线程再次确定在第一块中是否有任何剩余行（604）， 依次类推。

如果在第二块中有一个或多个剩余行（606为“是”），则不完整的内部 线程标识最小行（610）。最小行是第一块或者第二块中的剩余行中的最小的。 然后，不完整的内部线程将最小行插入到结果块中的最大行之后（612）。在 将最小行插入到结果块中之后，不完整的内部线程再次确定在第一块中是否有 任何剩余行（604），依次类推。

如果在第一块中没有剩余行（612为“否”），则不完整的内部线程确定 子线程是否完成（614）。当子线程向不完整的内部线程提供了完成指示时， 子线程完成。如果子线程还没有完成，则子线程仍可以继续向第一块中插入行。 因此，如果子线程没有完成（614为“否”），则不完整的内部线程等待（616）。 在不同的实施例中，不完整的内部线程等到不同的事件发生。例如，在某些实 施例中，不完整的内部线程等到计时器过期。在其他实施例中，不完整的内部 线程等到恢复事件发生。恢复事件可以是向第一块中插入行，来自子线程的完 成指示，或另一种类型的事件。在不完整的内部线程完成等待之后，不完整的 内部线程再次确定在第一块中是否有任何剩余行（604），依次类推。

如果子线程完成（614为“是”），则不完整的内部线程将第二块中的任 何剩余行都插入到结果块中的最大行之后（618）。如果当子线程完成时在第 二块中没有剩余行，则在步骤618中不完整的内部线程不向结果块中插入任何 行。

在将第二块程中的剩余行插入到结果块中之后，不完整的内部线程确定该 不完整的内部线程是否是根线程（620）。如果不完整的内部线程是根线程（620 为“是”），则不完整的内部线程向电子表格应用108提供完成指示（622）。 如果不完整的内部线程不是根线程（620为“否”），则不完整的内部线程向 不完整的内部线程的父线程提供完成指示（624）。在向电子表格应用108或 者父线程提供完成指示之后，不完整的内部线程休眠（626）。

图7是示出了由完整的内部线程所执行的示例操作700的流程图。虽然是 利用单个完整的内部线程来说明操作700的，但是，线程树中的每一完整的内 部线程都可以执行操作700。如图7的示例所示，当完整的内部线程被电子表 格应用108唤醒时（702）操作700开始。电子表格应用108向完整的内部线 程提供对第一块和第二块的引用。第一块是由完整的内部线程的第一子线程所 生成的结果块。第二块是由完整的内部线程的第二子线程所生成的结果块。完 整的内部线程，第一子线程，以及第二子线程在处理单元110的不同的处理单 元110上并行地操作。因此，当完整的内部线程执行操作700时，第一子线程 生成第一块，第二子线程生成第二块。此外，还由于完整的内部线程和第一子 线程并行地操作，因此，可能会有第一块不包含任何剩余行，但是第一子线程 以后会将更多行插入到第一块中的情况。同样，由于完整的内部线程和第二子 线程并行地操作，因此，可能会有第二块不包含任何剩余行，但是第二子线程 以后会将更多行插入到第二块中的情况。

在被唤醒之后，完整的内部线程确定在第一块中是否有任何剩余行（704）。 如果完整的内部线程确定在第一块中有一个或多个剩余行（704为“是”）， 则完整的内部线程确定在第二块中是否有任何剩余行（706）。

如果在第二数据块中没有剩余行（706为“否”），则完整的内部线程确 定第二子线程是否完成（708）。如果第二子线程向完整的内部线程提供了完 成指示，则第二子线程完成。如果第二子线程还没有完成，则第二子线程可以 向第二块中插入额外的行。这些行中的某些行可以小于第一块中的最小行。因 此，如果完整的内部线程确定第二子线程没有完成（708为“否”），则完整 的内部线程等待（710）。在不同的实施例中，完整的内部线程等到不同的事 件发生。例如，在某些实施例中，完整的内部线程等到计时器过期。在其他实 施例中，完整的内部线程等到完整的内部线程接收到恢复事件。恢复事件可以 指示第二线程已经将行插入到第二块中或第二线程完成。在完整的内部线程完 成等待之后，完整的内部线程再次确定第二块是否包括任何剩余行（706）， 依次类推。

如果第二子线程完成，则第二子线程将不会向第二块中插入更多行，在第 二块中没有剩余行。因此，第一块中的所有剩余行都大于结果块中的任何行。 因此，如果完整的内部线程确定第二子线程完成（708为“是”），则完整的 内部线程将第一块中的任何剩余行都插入到结果块中的最大行之后（712）。 在将第一块中的剩余行插入到结果块中之后，完整的内部线程再次确定在第一 块中是否有任何剩余行（704），依次类推。

如果完整的内部线程确定在第二块中有剩余行（706为“是”），则完整 的内部线程标识最小行（714）。最小行是第一块或者第二块中的剩余行中的 最小的。然后，完整的内部线程将最小行插入到结果块中的最大行之后（716）。 在将最小行插入到结果块中之后，完整的内部线程再次确定在第一块中是否有 任何剩余行（704），依次类推。

如果在第一块中没有剩余行（704为“否”），则完整的内部线程确定第 一子线程是否完成（718）。当第一子线程向完整的内部线程提供了完成指示 时，第一子线程完成。如果第一子线程还没有完成，则第一子线程仍可以继续 向第一块中插入行。因此，如果第一子线程没有完成（718为“否”），则完 整的内部线程等待（720）。在不同的实施例中，完整的内部线程等到不同的 事件发生。例如，在某些实施例中，完整的内部线程等到计时器过期。在其他 实施例中，完整的内部线程等到恢复事件发生。恢复事件可以是向第一块中插 入行，来自第一子线程的完成指示，或另一种类型的事件。

如果第一子线程完成（718为“是”），则完整的内部叶线程确定在第二 块中是否有任何剩余行（722）。如果在第二块中有一个或多个剩余行（722 为“是”），则完整的内部线程将第二块中的任何剩余行都插入到结果块中的 最大行之后（724）。完整的内部线程可以将第二块中的剩余行插入到结果块 中，因为第一子线程将不会向第一块中添加到任何额外的行，第一块中的所有 行都已经被添加到结果块中。因此，第二块中的任何剩余行都大于结果块中的 最大行。

在将第二块中的任何剩余行都插入到结果块中之后或在确定第二块中没 有剩余行之后（722为“否”），完整的内部线程确定第二子线程是否完成（726）。 如果完整的内部线程确定第二子线程没有完成（712为“否”），则完整的内 部线程等待（728）。在完整的内部线程完成等待之后，完整的内部线程再次 确定在第二块中是否有任何剩余行（722），依次类推。

如果完整的内部线程确定第二子线程完成（726为“是”），则完整的内 部线程确定完整的内部线程是否是根线程（730）。如果完整的内部线程是根 线程（730为“是”），则完整的内部线程向电子表格应用108提供完成指示 （732）。如果完整的内部线程不是根线程（730为“否”），则完整的内部线 程向完整的内部线程的父线程提供完成指示（734）。在向电子表格应用108 或者完整的内部线程的父线程提供完成指示后，完整的内部线程休眠（736）。

图8是示出了在排序过程的合并阶段由存储器管理线程所执行的示例操 作800的流程图。一些实施例使用涉及两个缓冲器的存储器管理技术。在这样 的实施例中，在块排序阶段所生成的经排序块中的每一个都存储在第一缓冲器 中。例如，图4的示例中所示出的块414、416、418、420、422、424，以及 426存储在第一缓冲器中。当叶线程生成结果块时，叶线程从第一缓冲器中读 取并将它们的结果块存储在第二缓冲器中。例如，图4的示例中所示出的线程 408、410，以及412将它们的结果块存储在第二缓冲器中。叶线程上方的第一 层中的内部线程从第二缓冲器中读取行，并将它们的结果块存回到第一缓冲器 中。例如，图4的示例中所示出的线程404和406从第二缓冲器中读取并将它 们的结果块存储到第一缓冲器中。叶线程上方的第二层中的内部线程从第一缓 冲器中读取行，并将它们的结果块存回到第二缓冲器中。例如，图4的示例中 所示出的线程402从第一缓冲器中读取并将其结果块存储到第二缓冲器中。对 于线程层次结构中的逐渐较高的层，继续。在某些情况下，此存储器管理技术 可以比为单个结果块分配存储器块更有效。

在使用此存储器管理技术的某些实施例中，电子表格应用108预期最终结 果块位于第一缓冲器中。然而，在某些情况下，最终结果块位于第二缓冲器中 而并非第一缓冲器中。此外，在使用此存储器管理技术的某些实施例中，给定 层中的所有合并线程都预期从同一个缓冲器中读取并将它们的结果块存储在 同一个缓冲器中。然而，不完整的内部线程读取由叶线程所产生的块（即，第 二缓冲器中的块）和在块排序阶段所生成的块（即，第一缓冲器中的块）。存 储器管理线程执行操作800以纠正这些问题。

如图8的示例所示，当存储器管理线程被电子表格应用108唤醒时（802） 操作800开始。在被唤醒之后，存储器管理线程确定是否有奇数数量的在排序 过程的块排序阶段所生成的经排序块（804）。如果在第一缓冲器有奇数数量 的块，则线程层次结构包括不完整的内部线程。因此，如果在第一缓冲器中有 奇数数量的块（804为“是”），则存储器管理线程将分配给不完整的内部线 程的块复制到第二缓冲器（806）。以此方式，块已准备好供不完整的内部线 程使用。

在将块复制到第二缓冲器之后或在确定没有奇数数量的在排序过程的块 排序阶段所生成的块之后（804为“否”），存储器管理线程确定最终结果块 是否完成（808）。如果最终结果块没有完成（808为“否”），则存储器管理 线程等待（810）。在不同的实施例中，存储器管理线程等到不同的事件发生。 例如，在某些实施例中，存储器管理线程等到计时器过期。在其他实施例中， 存储器管理线程等到根线程向电子表格应用108提供完成指示。在存储器管理 线程完成等待之后，存储器管理线程再次确定最终结果块是否完成（808）。

如果最终结果块完成（808为“是”），则存储器管理线程确定最终结果 块是否位于第二缓冲器中（812）。如果最终结果块位于第二缓冲器中（812 为“是”），则存储器管理线程将最终结果块复制到第一缓冲器中（814）。 在将最终结果块复制到第一缓冲器之后或在确定最终结果块已经在第一缓冲 器中之后（812为“否”），存储器管理线程休眠（816）。

图9是示出示例计算设备900的框图。在一些实施例中，计算系统100 是使用类似计算设备900的一个或多个计算设备来实现的。应当理解，在其他 实施例中，计算系统100是使用还具有除了图9的示例所示的硬件组件之外的 硬件组件的计算设备来实现的。

在不同的实施例中，计算设备以不同方式实现。例如，在图9的示例中， 计算设备900包括存储器902、处理系统904、辅助存储设备906、网络接口卡 908、视频接口910、显示设备912、外部组件接口914、外部存储设备916、 输入设备918、打印机920和通信介质922。在其他实施例中，计算设备是使 用更多或更少的硬件组件来实现的。例如，在另一示例实施例中，计算设备不 包括视频接口、显示设备、外部存储设备或输入设备。

存储器902包括一个或多个能够存储数据和/或指令的计算机可读数据存 储介质。如在本文档中所使用的，计算机可读数据存储介质是一种存储计算设 备可读的数据和/或软件指令的设备或制品。在不同的实施例中，存储器902 以不同的方式实现。例如，在各实施例中，存储器902是使用各种类型的计算 机可读数据存储介质来实现的。示例类型的计算机可读数据存储介质包括，但 不限于：动态随机存取存储器（DRAM）、双倍数据率同步动态随机存取存储 器(DDR SDRAM)、减少等待时间的DRAM、DDR2 SDRAM、DDR3 SDRAM、 Rambus RAM、固态存储器、闪存、只读存储器（ROM）、电可擦除可编程 ROM和存储数据的其他类型的设备和/或制品。

处理系统904包括选择性地执行软件指令的一个或多个物理集成电路。在 各种实施例中，处理系统904以各种方式实现。例如，在一个示例实施例中， 处理系统904被实现为一个或多个处理核。例如，在该示例实施例中，处理系 统904可被实现为一个或多个Intel Core 2微处理器。在另一示例实施例中，处 理系统904可被实现为一个或多个单独的微处理器。在又一示例实施例中，处 理系统904被实现为提供专用功能的ASIC。在又另一示例实施例中，处理系 统904通过使用ASIC和通过执行软件指令来提供专用功能。

在不同的实施例中，处理系统904执行不同的指令集中软件指令。例如， 在各实施例中，处理系统904执行指令集中的软件指令，所述指令集为诸如x86 指令集、POWER指令集、RISC指令集、SPARC指令集、IA-64指令集、MIPS 指令集，和/或其他指令集。

辅助存储设备906包括一个或多个计算机可读数据存储介质。辅助存储设 备906存储了所述处理系统904不能直接访问的数据和软件指令。换言之，处 理系统904执行I/O用于从辅助存储设备906处检索数据和/或软件指令。在各 实施例中，辅助存储设备906由各种类型的计算机可读数据存储介质来实现。 例如，辅助存储设备906可以由一个或多个磁盘、磁带驱动器、CD-ROM盘、 DVD-ROM盘、蓝光盘、固态存储设备、柏努利录音带（Bernoulli cartridges） 和/或其他类型的计算机可读数据存储介质来实现。

网络接口卡908使得计算设备900能够将数据发送给计算机通信网络并从 计算机通信网络接收数据。在不同的实施例中，网络接口卡908以不同的方式 实现。例如，在各种实施例中，网络接口卡908可以被实现为太网接口、令牌 环网络接口、光纤网络接口、无线网络接口（例如，WiFi、WiMax等）、或 另一类型的网络接口。

视频接口910使计算设备900能够将视频信息输出给显示设备912。在不 同的实施例中，视频接口910以不同的方式实现。例如，在一个示例实施例中， 视频接口910被集成到计算设备900的主板上。在另一个示例实施例中，视频 接口910是视频扩展卡。示例类型的视频扩展卡包括由安大略省马克姆市的 ATI Technologies有限公司制造的Radeon图形卡、由加利福尼亚州圣克拉拉市 的Nvidia（英伟达）公司制造的Geforce图形卡和其他类型的图形卡。

在各实施例中，显示设备912被实现为各种类型的显示设备。示例类型的 显示设备包括但不限于：阴极射线管显示器、LCD显示面板、等离子屏显示面 板、触敏显示面板、LED屏幕、投影仪和其他类型的显示设备。在各实施例中， 视频接口910以各种方式与显示设备512通信。例如，在各实施例中，视频接 口910可以经由通用串行总线（USB）连接器、VGA连接器、数字可视接口 （DVI）连接器、S视频连接器、高清多媒体接口（HDMI）接口、显示端口连 接器或其他类型的连接来与显示设备912通信。

外部组件接口914使计算设备900能够与外部设备通信。在各实施例中， 外部组件接口914以不同的方式实现。例如，在一个示例实施例中，外部组件 接口914是USB接口。在其他示例实施例中，计算设备900是火线接口、串 行端口接口、并行端口接口、PS/2接口和/或使计算设备900能够与外部组件 通信的另一种类型的接口。

在不同的实施例中，外部组件接口914使计算设备900能够与不同的外部 组件通信。例如，在图9的示例中，外部组件接口914使计算设备900能够与 外部存储设备916、输入设备918和打印机920通信。在其他实施例中，外部 组件接口914使计算设备900能够与更多或更少的外部组件通信。其他示例类 型的外部组件包括但不限于：扬声器、电话充电插口、调制解调器、媒体播放 器底座、其他计算设备、扫描仪、数码相机、指纹读取器、以及可被连接到计 算设备900的其他设备。

外部存储设备916是包括一个或多个计算机可读数据存储介质的外部组 件。计算设备900的不同实现与不同类型的外部存储设备对接。示例类型的外 部存储设备包括但不局限于：磁带驱动器、闪存模块、磁盘驱动器、光盘驱动 器、闪存单元、zip盘驱动器、自动换碟机以及包括一个或多个计算机可读数 据存储介质的其他类型的设备。输入设备918是向计算设备900提供用户输入 的外部组件。计算设备900的不同实现与不同类型的输入设备对接。示例类型 的输入设备包括，但不局限于，键盘、鼠标、轨迹球、笔输入设备、按键式拨 号盘、麦克风、操纵杆、触敏显示屏以及将用户输入提供给计算设备900的其 他类型的设备。打印机920是将数据打印到纸张的外部设备。计算设备900的 不同实现与不同类型的打印机对接。示例类型的打印机包括但不限于：激光打 印机、喷墨打印机、照片打印机、复印机、传真机、票据打印机、点阵打印机 或将数据打印到纸张的其他类型的设备。

通信介质922方便了在计算设备900的硬件组件之间的通信。在不同的实 施例中，通信介质922方便了在计算设备900的不同组件之间的通信。例如， 在图9的示例中，通信介质922方便了在存储器902、处理系统904、辅助存 储设备906、网络接口卡908、视频接口910以及外部组件接口914之间的通 信。在计算设备900的不同的实现中，通信介质922可以以不同的方式来实现. 例如，在计算设备900的不同的实现中，通信介质922可作为PCI总线、PCI Express总线、加速图形端口（AGP）总线、Infiniband互连、串行高级技术附 件（ATA）互连、并行ATA互连、光纤通道互连、USB总线、小型计算系统 接口（SCSI）接口，或其他类型的通信媒介来实现。

存储器902存储了各种类型的数据和/或软件指令。例如，在图9的示例 中，存储器902存储了基本输入/输出系统（BIOS）924、操作系统926、应 用软件928和程序数据930。BIOS 924包括当由处理系统904执行时使得计算 设备900启动的一组软件指令。操作系统926包括当由处理系统904执行时使 得计算设备900提供操作系统的一组软件指令，所述操作系统协调计算设备 900的活动和资源的共享。示例类型的操作系统包括但不限于：微软Linux、Unix、苹果OS X、苹果OS X iPhone、Palm webOS、Palm OS、谷歌 Chrome OS、谷歌Android OS等等。应用软件928包括一组软件指令，该组软 件指令在被处理系统904执行时使得计算设备900向计算设备900的用户提供 应用。程序数据930是应用软件928生成和/或使用的数据。

上述各实施例仅作为说明提供，并且不应被解释为限制。本领域的技术人 员将容易地识别出可能不遵循在此说明并描述的示例实施例和应用而做出的 各种修改和变化。例如，在图中示出的操作仅仅是示例。在各种实施例中，类 似的操作可以包括比在图中所示出的那些步骤更多或更少的步骤。而且，在其 他实施例中，类似的操作可以包括与在图中所示出的那些操作步骤不相同的次 序的步骤。