Back to results
US 10,002,147 B2Granted
Merging of sorted lists using array pair
AssigneeMicrosoft Technology Licensing, LLC
InventorsJonathan David Goldstein, Badrish Chandramouli
Life of this patent
Estimating the term…
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 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.
Claims20
A computing system comprising:
- one or more processors;
- and
- one or more hardware storage devices having stored computer-executable instructions which are executable by the one or more processors to implement a method for merging a plurality of sorted lists to form a merged sorted list, wherein the method includes:
- an act of accessing a plurality of sorted lists including a first sorted list and a second sorted list in a first array in memory;
- an act of establishing a first reference to a first element in the first sorted list in the first array;
- an act of establishing a second reference to the first element in the second sorted list in the first array;
- an act of formulating a second array in memory, the second array including at least a portion that includes a second plurality of elements equal in number to the first plurality of elements;
- an act of sequentially assigning values to the elements of the second plurality of elements to thereby formulated a first merged sorted list of the first and second sorted lists,
- the act of sequentially assigning comprising performing the following for each of the first element through a subsequent element in the secondary plurality of elements:
- an act of comparing a value at an element referenced by the first reference with a value at the element referenced by the second reference;
- if the value at the element referenced by the first reference satisfies a sorting priority with respect to the value at the element corresponding to the second reference, an act of populating the corresponding element of the second plurality of elements with the value at the element referenced by the first reference, and an act of causing the first reference to reference a next element in the first sorted list of the first plurality of elements if there are any further elements in the first sorted list, and if there are not any further elements in the first sorted list, the corresponding element of the second plurality of elements is the subsequent element of the second plurality of elements, and thus the method further includes an act of further populating a remainder of the second plurality of elements with any remaining unprocessed elements of the second sorted list from an element referenced by the second reference;
- and
- if the value at the element referenced by the first reference does not satisfy a sorting priority with respect to the value at the element referenced by the second reference, an act of populating the corresponding element of the second plurality of elements with the value at the element referenced by the second reference, and an act of causing the second reference to reference a next element in the second sorted list of the first plurality of elements if there are any further elements in the second sorted list, and if there are not any further elements in the second sorted list, the corresponding element of the second plurality of elements is the subsequent element of the second plurality of elements, and thus the method further includes an act of further populating a remainder of the second plurality of elements with any remaining unprocessed elements of the first sorted list from an element referenced by the first reference.
10 more elements
A computer program product comprising one or more computer-readable storage media having thereon computer-executable instructions that are structured such that, when executed by one or more processors of the computing system, cause the computing system to perform a method comprising an act of merging a plurality of sorted lists to form a merged sorted list, the act merging the plurality of sorted lists comprising:
- an act of accessing a plurality of sorted lists including a first sorted list and a second sorted list in a first array in memory;
- an act of establishing a first reference to a first element in the first sorted list in the first array;
- an act of establishing a second reference to the first element in the second sorted list in the first array;
- an act of formulating a second array in memory, the second array including at least a portion that includes a second plurality of elements equal in number to the first plurality of elements;
- an act of sequentially assigning values to the elements of the second plurality of elements to thereby formulated a first merged sorted list of the first and second sorted lists,
- the act of sequentially assigning comprising performing the following for each of the first element through a subsequent element in the secondary plurality of elements:
- an act of comparing a value at an element referenced by the first reference with a value at the element referenced by the second reference;
- if the value at the element referenced by the first reference satisfies a sorting priority with respect to the value at the element corresponding to the second reference, an act of populating the corresponding element of the second plurality of elements with the value at the element referenced by the first reference, and an act of causing the first reference to reference a next element in the first sorted list of the first plurality of elements if there are any further elements in the first sorted list, and if there are not any further elements in the first sorted list, the corresponding element of the second plurality of elements is the subsequent element of the second plurality of elements, and thus the method further includes an act of further populating a remainder of the second plurality of elements with any remaining unprocessed elements of the second sorted list from an element referenced by the second reference;
- and
- if the value at the element referenced by the first reference does not satisfy a sorting priority with respect to the value at the element referenced by the second reference, an act of populating the corresponding element of the second plurality of elements with the value at the element referenced by the second reference, and an act of causing the second reference to reference a next element in the second sorted list of the first plurality of elements if there are any further elements in the second sorted list, and if there are not any further elements in the second sorted list, the corresponding element of the second plurality of elements is the subsequent element of the second plurality of elements, and thus the method further includes an act of further populating a remainder of the second plurality of elements with any remaining unprocessed elements of the first sorted list from an element referenced by the first reference.
7 more elements
A method comprising an act of merging a plurality of sorted lists to form a merged sorted list, the method comprising:
- an act of accessing a plurality of sorted lists including a first sorted list and a second sorted list in a first array in memory;
- an act of establishing a first reference to a first element in the first sorted list in the first array;
- an act of establishing a second reference to the first element in the second sorted list in the first array;
- an act of formulating a second array in memory, the second array including a portion that includes a second plurality of elements equal in number to the first plurality of elements;
- an act of sequentially assigning values to at least some of the elements of the second plurality of elements, the act of sequentially assigning comprising:
- an act of populating a first element of the second plurality of elements, the act of populating the first element comprising:
- an act of comparing a value at an element referenced by the first reference with a value at the element referenced by the second reference;
- if the value at the element referenced by the first reference satisfies a sorting priority with respect to the value at the element referenced by the second reference;
- an act of populating the first element of the second plurality of elements with the value at the element referenced by the first reference;
- and an act of causing the first reference to reference a next element, if any, in the first sorted list of the first plurality of elements;
- and
- if the value at the element referenced by the first reference does not satisfy a sorting priority with respect to the value at the element referenced by the second reference;
- an act of populating the first element of the second plurality of elements with the value at the element referenced by the second reference;
- and an act of causing the second reference to reference a next element, if any, in the second sorted list of the first plurality of elements;
- and
- an act of populating a second element of the second plurality of elements after the act of populating the first element of the second plurality of elements, the act of populating the second element comprising:
- an act of comparing a value at an element referenced by the first reference with a value at the element referenced by the second reference;
- if the value at the element referenced by the first reference satisfies the sorting priority with respect to the value at the element referenced by the second reference;
- an act of populating the second element of the second plurality of elements with the value at the element referenced by the first reference;
- and
- if the value at the element referenced by the first reference does not satisfy the sorting priority with respect to the value at the element referenced by the second reference;
- an act of populating the second element of the second plurality of elements with the value at the element referenced by the second reference.
19 more elements
Dependencies are inferred from the claim text.