US 12,585,399 B2 · In-place sorting

Abstract

Implementations described herein relate to improved in-place sample sorting of data. In various implementations, unsorted elements of a set stored in a first memory segment may be compared to splitter values to determine respective counts of elements of the set that will fit into each of a plurality of buckets bounded by the splitter values. Some number of elements from each of multiple ranges of the first memory segment that correspond to the multiple buckets may be moved to a smaller second memory segment. Remaining elements may be redistributed from at least some of the plurality of ranges of the first memory segment across the plurality of ranges based on comparing the remaining elements to the splitter values. The elements from the second memory segment may then be distributed across the plurality of ranges based on comparing the elements to the splitter values.

Claims20

Dependent claims

A method implemented using one or more processors and comprising:

comparing elements of a set of unsorted elements stored in a first memory segment to a plurality of splitter values;
based on the comparing, determining respective counts of elements of the set that will fit into each of a plurality of buckets bounded by the splitter values;
determining a predetermined number of elements to be moved from the first memory segment to a second memory segment that is smaller than the first memory segment;
moving, to the second memory segment, the same predetermined number of elements from each of a plurality of ranges of the first memory segment that correspond to the plurality of buckets;
while the predetermined number of elements remain in the second memory segment, redistributing remaining elements from at least some of the plurality of ranges of the first memory segment across the plurality of ranges based on comparing the remaining elements to the splitter values;
and
distributing the elements from the second memory segment across the plurality of ranges based on comparing the elements to the splitter values.

4 more elements

A system comprising one or more processors and memory storing instructions that, in response to execution by the one or more processors, cause the one or more processors to:

compare elements of a set of unsorted elements stored in a first memory segment to a plurality of splitter values;
based on the comparing, determine respective counts of elements of the set that will fit into each of a plurality of buckets bounded by the splitter values;
determine a predetermined number of elements to be moved from the first memory segment to a second memory segment that is smaller than the first memory segment;
move, to the second memory segment, the same predetermined number of elements from each of a plurality of ranges of the first memory segment that correspond to the plurality of buckets;
while the predetermined number of elements remain in the second memory segment, redistribute remaining elements from at least some of the plurality of ranges of the first memory segment across the plurality of ranges based on comparing the remaining elements to the splitter values;
and
distribute the elements from the second memory segment across the plurality of ranges based on comparing the elements to the splitter values.

4 more elements

Dependencies are inferred from the claim text.

In-place sorting

Life of this patent

In-place sorting

Life of this patent

Abstract

Claims20