Multi-threaded sort of data items in spreadsheet tables

A computing system comprising:

• a processing system comprising a plurality of processing units;
• and
• a data storage system comprising computer-readable instructions that, when executed by one or more of the processing units, cause the computing system to:
• divide data items in a spreadsheet table into a plurality of blocks;
• use multiple block sorting threads to sort the data items in the blocks, wherein the number of the block sorting threads is equal to the number of the blocks;
• after the data items in the blocks are sorted, use multiple merge threads to generate a final result block, the final result block containing each of the data items in the spreadsheet table, each of the merge threads being a thread that merges two source blocks to generate a result block, each of the source blocks being either one of the sorted blocks or one of the result blocks generated by another one of the merge threads;
• and
• display a sorted version of the spreadsheet table, data items in the sorted version of the spreadsheet table being ordered according to an order of the data items in the final result block, wherein the merge threads include an incomplete interior thread when the number of blocks in the plurality of blocks is odd, wherein the computer-readable instructions, when executed by one or more of the processing units, further cause the computing system to assign one of the blocks to the incomplete interior thread, wherein the incomplete interior thread generates a result block that contains each of the data items in a result block generated by a child thread of the incomplete interior thread and the block assigned to the incomplete interior thread, the data items in the result block generated by the incomplete interior thread being properly ordered, the child thread being another one of the merge threads.

A method comprising:

• dividing data items in a spreadsheet table into a plurality of blocks;
• using multiple threads to sort the data items in the blocks;
• after the data items in the blocks are sorted, using, by a computing system, multiple merge threads to generate a final result block, the final result block containing each of the data items in the spreadsheet table, each of the merge threads being a thread that merges two source blocks to generate a result block, each of the source blocks being either one of the sorted blocks or one of the result blocks generated by another one of the merge threads, the merge threads including a leaf thread that performs the following actions:
• determining whether there are any remaining data items in a first block assigned to the leaf thread, the first block being one of the sorted blocks;
• performing the following actions while there are one or more data items in the first block:
• determining whether there are any remaining data items in a second block assigned to the leaf thread, the second block being another one of the sorted blocks;
• performing the following actions when there are one or more data items in the second block:
• identifying a minimum data item, the minimum data item being a smallest of the remaining data item in the first block and the second block;
• inserting the minimum data item into a result block generated by the leaf thread after a largest data item in the result block;
• inserting, when there are no remaining data items in the second block, any remaining data items in the first block into the result block generated by the leaf thread after the largest data item in the result block generated by the leaf thread;
• and
• inserting, when there are no remaining data items in the first block, any remaining data items in the second block into the result block after the largest data item in the result block generated by the leaf thread;
• and
• displaying a sorted version of the spreadsheet table, data items in the sorted version of the spreadsheet table being ordered according to an order of the data items in the final result block.