Merging of sorted lists using array pair

Patent metadata

Field	Value
Publication number	US-10552397-B2
Application number	US-201615232315-A
Country	US
Kind code	B2
Filing date	Aug 9, 2016
Priority date	May 13, 2013
Publication date	Feb 4, 2020
Grant date	Feb 4, 2020

Abstract

The formulation of a merged sorted list from multiple input sorted lists in multiple phases using an array pair. Initially, the first array is contiguously populated with the input sorted lists. In the first phase, the first and second input sorted lists are merged into a first intermediary merged list within the second array. Each subsequent phase merges a prior intermediary merged list resulting from the prior phase and, a next input sorted list in the first array to generate a next intermediary merged list, or a merged sorted list if there or no further input in the first array. The intermediary merged lists alternate between the first array and the second array from one phase to the next phase.

First claim

What is claimed is:

1. A computing system comprising:
one or more hardware processors; and
one or more storage devices having stored computer-executable instructions that are executable by the one or more hardware processors for implementing a method for formulating a merged sorted list, wherein the method includes:
an act of accessing a plurality of input sorted lists including three or more input sorted lists;
an act of contiguously populating a first array with the plurality of input sorted lists; and
an act of using the first array and a second array to merge the plurality of input sorted lists into a merged sorted list, wherein the merging occurs by merging the first and second sorted lists in a plurality of phases, wherein the merging of the first and second sorted lists occurs in a first phase of the plurality of phases and results in a first intermediary merged list, and wherein the plurality of phases includes:
a subsequent plurality of phases each merging a prior intermediary merged list resulting from a prior phase of the plurality of phases with a next input sorted list of the plurality of input sorted lists to generate a next intermediary merged list, and a final merged sorted list when there or no further input sorted lists after the next input sorted list in the plurality of input sorted lists; and
alternating a location in memory for the next intermediary merged list, for each of the subsequent plurality of phases, between the first array and the second array from one phase of the plurality of phases to the next phase of the subsequent plurality of phases.

2. The computing system in accordance with claim 1 , wherein the act of accessing the plurality of input sorted lists further comprises:
an act of accessing a plurality of elements; and
an act of using the plurality of elements to formulate the plurality of input sorted lists.

3. The computing system in accordance with claim 2 , wherein the act of using the plurality of elements to formulate the plurality of input sorted lists further comprises the following, for each of the plurality of elements:
an act of determining whether or not there are any input sorted lists that have a tail member that has a higher priority in a sorting priority than the corresponding element,
if there are not any input sorted lists that have a tail member than has a higher priority in the sorting priority than the corresponding element, an act of creating a new input sorted list and an act of adding the corresponding element as a head element of the new input sorted list, the corresponding element also being a tail element of the new input sorted list since the corresponding element is the only element of the new input sorted list; and
if there are one or more input sorted lists that have a tail member that has a higher priority in the sorting priority than the corresponding element, an act of adding the corresponding element to one of the one or more input sorted lists such that the corresponding element becomes a new tail member of the input sorted list to which the corresponding element is added.

4. The computing system in accordance with claim 3 , wherein the method further includes:
an act of selecting whichever of the multiple sorted lists have a tail member that has a lowest priority in the sorting priority as the input sorted list to which to add the corresponding element as a new tail member when there are multiple input sorted lists that have a tail member that has a higher priority in the sorting priority than the corresponding element.

5. The computing system in accordance with claim 4 , wherein the input sorted lists are ordered in sequence of lower to higher priority of each tail member in the sorting priority.

6. The computing system in accordance with claim 5 , wherein for a given element of the plurality of elements, the act of determining whether or not there are any input sorted lists that have a tail member that has a higher priority in a sorting priority than the corresponding element, and the act of selecting whichever of the multiple input sorted lists has a tail member that has a lowest priority in the sorting priority as the sorted list to which to add the corresponding element as a new tail member, comprises the following:
an act of marking a last input sorted list to which a prior element of the plurality of elements was added;
an act of beginning a comparison of the given element with the tail member of the marked sorted list.

7. One or more storage devices having stored computer-executable instructions that are executable by one or more hardware processors for causing a computing system to implement a method of formulating a merged sorted list, wherein the method includes:
an act of accessing a plurality of input sorted lists including three or more input sorted lists;
an act of contiguously populating a first array with the plurality of input sorted lists; and
an act of using the first array and a second array to merge the plurality of input sorted lists into a merged sorted list, wherein the merging occurs by merging the first and second sorted lists in a plurality of phases, wherein the merging of the first and second sorted lists occurs in a first phase of the plurality of phases and results in a first intermediary merged list, and wherein the plurality of phases includes:
a subsequent plurality of phases each merging a prior intermediary merged list resulting from a prior phase of the plurality of phases with a next input sorted list of the plurality of input sorted lists to generate a next intermediary merged list, and a final merged sorted list when there or no further input sorted lists after the next input sorted list in the plurality of input sorted lists; and
alternating a location in memory for the next intermediary merged list, for each of the subsequent plurality of phases, between the first array and the second array from one phase of the plurality of phases to the next phase of the subsequent plurality of phases.

8. The one or more storage devices in accordance with claim 7 , wherein the act of accessing the plurality of input sorted lists further comprises:
an act of accessing a plurality of elements; and
an act of using the plurality of elements to formulate the plurality of input sorted lists.

9. The one or more storage devices in accordance with claim 8 , wherein the act of using the plurality of elements to formulate the plurality of input sorted lists further comprises the following, for each of the plurality of elements:
an act of determining whether or not there are any input sorted lists that have a tail member that has a higher priority in a sorting priority than the corresponding element,
if there are not any input sorted lists that have a tail member than has a higher priority in the sorting priority than the corresponding element, an act of creating a new input sorted list and an act of adding the corresponding element as a head element of the new input sorted list, the corresponding element also being a tail element of the new input sorted list since the corresponding element is the only element of the new input sorted list; and
if there are one or more input sorted lists that have a tail member that has a higher priority in the sorting priority than the corresponding element, an act of adding the corresponding element to one of the one or more input sorted lists such that the corresponding element becomes a new tail member of the input sorted list to which the corresponding element is added.

10. The one or more storage devices in accordance with claim 9 , wherein the method further includes:
an act of selecting whichever of the multiple sorted lists have a tail member that has a lowest

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Goldstein Jonathan David
• Chandramouli Badrish

Classifications

• G06F16/217

  Database tuning (G06F16/2282 takes precedence; database performance monitoring G06F11/3409) · CPC title

• G06F16/2237 Primary

  Vectors, bitmaps or matrices · CPC title

• G06F16/245

  Query processing · CPC title

• G06F2207/224

  External sorting · CPC title

• G06F7/32 Primary

  Merging, i.e. combining data contained in ordered sequence on at least two record carriers to produce a single carrier or set of carriers having all the original data in the ordered sequence {merging methods in general}(G06F7/36 takes precedence) · CPC title