# US 2016/0350345 A1 · Merging of sorted lists using array pair

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2016/0350345 A1
- Document ID: US20160350345A1
- Status: Published application
- Kind: A1
- Application number: 15/232,315
- Filed: 2016-08-09
- Published: 2016-12-01
- Earliest claimed: 2013-05-13
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Jonathan David Goldstein; Badrish Chandramouli
- Web page: https://patentgrep.com/patent/US20160350345A1

## CPC

- G06F 16/2237: {Vectors, bitmaps or matrices}
- G06F 7/32: 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)
- G06F 16/217: {Database tuning (G06F16/2282 takes precedence; database performance monitoring G06F11/3409)}
- G06F 16/22: Indexing; Data structures therefor; Storage structures
- G06F 16/245: Query processing
- G06F 2207/224: External sorting
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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.

## Claims

### Claim 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;
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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 3)

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,

### Claim 5 (depends on 4)

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.

### Claim 6 (depends on 5)

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.

### Claim 7 (depends on 1)

The computing system in accordance with claim 1, wherein the merging occurs 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, or a merged sorted list if there or no further input sorted lists after the next input sorted list in the plurality of input sorted lists,
wherein a location of the intermediary merged list alternates between the first array and the second array from one phase of the plurality of phases to the next phase of the plurality of phases.

### Claim 8

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;
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.

### Claim 9 (depends on 8)

The one or more storage devices in accordance with claim 8, 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.

### Claim 10 (depends on 9)

The one or more storage devices in accordance with claim 9, 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.

### Claim 11 (depends on 10)

The one or more storage devices in accordance with claim 10, 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,

### Claim 12 (depends on 11)

The one or more storage devices in accordance with claim 11, wherein the input sorted lists are ordered in sequence of lower to higher priority of each tail member in the sorting priority.

### Claim 13 (depends on 12)

The one or more storage devices in accordance with claim 12, 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.

### Claim 14 (depends on 8)

The one or more storage devices in accordance with claim 8, wherein the merging occurs 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, or a merged sorted list if there or no further input sorted lists after the next input sorted list in the plurality of input sorted lists,
wherein a location of the intermediary merged list alternates between the first array and the second array from one phase of the plurality of phases to the next phase of the plurality of phases.

### Claim 15

A method for formulating a merged sorted list, the method comprising:
an act of accessing a plurality of 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.

### Claim 16 (depends on 15)

The method in accordance with claim 15, wherein the act of accessing the plurality of input sorted lists 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.

### Claim 17 (depends on 16)

The method in accordance with claim 16, wherein the act of using the plurality of elements to formulate the plurality of input sorted lists 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; and either
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 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, wherein the corresponding element is a tail element of the new input sorted list since the corresponding element is an only element of the new input sorted list, or alternatively
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 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.

### Claim 18 (depends on 17)

The method in accordance with claim 17, 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 in response to detecting multiple input sorted lists that have a tail member that has a higher priority in the sorting priority than the corresponding element.

### Claim 19 (depends on 18)

The method in accordance with claim 18, wherein the input sorted lists are ordered in sequence of lower to higher priority of each tail member in the sorting priority, wherein the method further includes, for a given element of the plurality of elements, 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.

### Claim 20 (depends on 15)

The method in accordance with claim 15, wherein the merging occurs 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, the plurality of phases further comprising:
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, or a merged sorted list if there or no further input sorted lists after the next input sorted list in the plurality of input sorted lists,
wherein a location of the intermediary merged list alternates between the first array and the second array from one phase of the plurality of phases to the next phase of the plurality of phases.
