Multi-Threaded Sort of Data Items in Spreadsheet Tables

1 . A method comprising:

dividing, by a computing system, data items in a spreadsheet table into a plurality of blocks;

using multiple threads to sort the data items in the blocks;

after sorting the data items in the blocks, using multiple threads to merge the blocks into a final block, the final block containing each of the data items in the spreadsheet table; and

displaying a sorted version of the spreadsheet table in which data items in the spreadsheet table have the same order as an order of data items in the final block.

2 . The method of claim 1 , further comprising:

determining an appropriate block size based on a number of data items in the spreadsheet table; and

wherein the data items in the spreadsheet table are divided into the plurality of blocks such that none of the blocks contains more data items than the appropriate block size and only one of the blocks is allowed to contain fewer data items than the appropriate block size.

3 . The method of claim 2 , wherein determining the appropriate block size comprises determining that the appropriate block size is a given size when the total number of data items in the spreadsheet table is greater than one threshold and less than or equal to another threshold.

4 . The method of claim 1 , wherein the data items in the final block are properly ordered for multiple sort-by columns.

5 . The method of claim 1 , further comprising:

determining whether a total number of data items in the spreadsheet table exceeds a lower limit; and

using a single thread to sort the data items in the spreadsheet table when the total number of data items in the spreadsheet table does not exceed the lower limit.

6 . The method of claim 1 ,

wherein the method further comprises: prior to sorting the data items in the blocks, determining an appropriate number of block sorting threads for the spreadsheet table;

wherein using multiple threads to sort the data items in the blocks comprises using the appropriate number of block sorting threads to sort the data items in the blocks;

wherein the appropriate number of block sorting threads is equal to a number of the blocks when the number of the blocks is less than or equal to a number of processing units in a processing system,

wherein the appropriate number of block sorting threads is equal to the number of processing units in the processing system when the number of blocks is greater than or equal to the number of processing units in the processing system.

7 . The method of claim 6 , further comprising: presenting a user interface that allows an administrative user to set the appropriate number of block sorting threads.

8 . The method of claim 1 , wherein using multiple threads to sort the data items in the blocks comprises using a merge sort algorithm to sort the data items in the blocks.

9 . The method of claim 1 , wherein using multiple threads to merge the blocks into the final block comprises:

waking a min merge thread that progressively inserts smallest data items in the sorted blocks into the final block; and

waking a max merge thread that progressively inserts largest data items in the sorted blocks into the final block.

10 . The method of claim 9 ,

wherein the min merge thread uses a first red-black tree to identify the smallest data items in the sorted blocks; and

wherein the max merge thread uses a second red-black tree to identify the largest data items in the sorted blocks.

11 . The method of claim 9 , wherein the min merge thread and the max merge thread operate concurrently.

12 . The method of claim 1 , wherein displaying the sorted version of the spreadsheet table comprises: sending result data to a client device via a network, the client device configured to process the result data for presentation of the sorted version of the spreadsheet table to a user.

13 . The method of claim 1 , wherein the multiple threads used to sort the data items in the blocks operate concurrently.

14 . A computing system comprising:

a processing system that comprises a plurality of processing units; and

a data storage system that stores computer-readable instructions that, when executed by one or more of the processing units, cause the computing system to:

divide the data items in a spreadsheet table into a plurality of blocks;

use multiple threads to sort the data items in the blocks based on a relevant property of cells in a sort-by line of the spreadsheet table;

use multiple threads to merge the blocks into a final block, the final block containing each of the data items in the spreadsheet table; and

display a sorted version of the spreadsheet table in which data items in the spreadsheet table have the same order as an order of the data items in the final block.

15 . The computing system of claim 14 , wherein the computer-readable instructions, when executed by one or more of the processing units, cause the computing system to determine an appropriate block size based on the number of data items in the spreadsheet table, wherein none of the blocks has more data items than the appropriate block size.

16 . The computing system of claim 14 , wherein the computer-readable instructions, when executed by one or more of the processing units, further cause the computing system to determine an appropriate number of block sorting threads,

wherein the appropriate number of block sorting threads is equal to a number of the blocks when the number of the blocks is less than or equal to a number of the processing units in the processing system,

wherein the appropriate number of block sorting threads is equal to the number of processing units in the processing system when the number of blocks is greater than or equal to the number of processing units in the processing system, and

wherein the computing system uses the appropriate number of block sorting threads to sort the data items in the blocks.

17 . The computing system of claim 14 , wherein to use multiple threads to merge the blocks into the final block, the computer-readable instructions, when executed by one or more of the processing units, cause the computing system to:

wake a min merge thread that progressively inserts smallest data items in the sorted blocks into the final block; and

wake a max merge thread that progressively inserts largest data items in the sorted blocks into the final block.

18 . The method of claim 17 ,

wherein the min merge thread uses a first red-black tree to identify the smallest data items in the sorted blocks; and

wherein the max merge thread uses a second red-black tree to identify the largest data items in the sorted blocks.

19 . The computing system of claim 17 ,

wherein the min merge thread and the max merge thread operate concurrently; and

wherein the multiple threads used to sort the data items in the blocks operate concurrently.

20 . A computer-readable data storage medium that stores computer-readable instructions that, when executed by one or more processing units in a processing system of a computing system, cause the computing system to:

determine whether a total number of data items in a spreadsheet table exceeds a lower limit;

when the total number of data items in the spreadsheet table does not exceed the lower limit, use a single thread to sort the data items in the spreadsheet table;

when the total number of data items in the spreadsheet table is equal to or exceeds the lower limit:

determine that an appropriate block size is a first size when the total number of data items in the spreadsheet table is greater than a first threshold and less than or equal to a second threshold;

determine that the appropriate block size is a second size when the total number of data items in the spreadsheet table is greater than the second threshold, the second size being larger than the first size;

divide the data items in the spreadsheet table into a plurality of blocks, none of the blocks containing more data items than the appropriate block size and only one of the blocks being allowed to contain fewer data items than the appropriate block size;

determine an appropriate number of block sorting threads for the spreadsheet table,

wherein the appropriate number of block sorting threads is equal to a number of the blocks when the number of the blocks is less than or equal to a number of the processing units in the processing system,

wherein the appropriate number of block sorting threads is equal to the number of processing units in the processing system when the number of blocks is greater than or equal to the number of processing units in the processing system,

use a plurality of block sorting threads to sort the data items in the blocks, the block sorting threads being equal in number to the appropriate number of block sorting threads; and

after the block sorting threads have sorted the data items in each of the blocks, use a min merge thread and a max merge thread to merge the data items in the blocks into a final block, the final block containing each of the data items in the spreadsheet table, the min merge thread progressively inserting smallest data items in the sorted blocks into the final block, the max merge thread progressively inserting largest data items in the sorted blocks into the final block; and

display a sorted version of the spreadsheet table in which data items in the spreadsheet table have the same order as an order of data items in the final block.