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 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.
Claims17
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.
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.
A method for formulating a merged sorted list, the method comprising:
- 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 computer-readable 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.
Dependencies are inferred from the claim text.