# US 2017/0286459 A1 · Increasing radix sorting efficiency utilizing a crossover point

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

- Number: US 2017/0286459 A1
- Document ID: US20170286459A1
- Status: Published application
- Kind: A1
- Application number: 15/084,626
- Filed: 2016-03-30
- Published: 2017-10-05
- Earliest claimed: 2016-03-30
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Lee C. Chu; Joshua R. Tiefenbach
- Web page: https://patentgrep.com/patent/US20170286459A1

## CPC

- G06F 7/24: Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers {sorting methods in general}(G06F7/36 takes precedence)
- G06F 7/36: Combined merging and sorting
- 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/284: {Relational databases}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Embodiments of the present invention provide a method, computer program product and system for increasing sorting efficiency by utilizing a determined crossover point. Initially, a set of data, containing a number of tuples, to be sorted is received. A determination is made as to the number of radix sort iterations to perform based on the number of tuples of the received data. A countdown timer is set based on the determined number of radix sort iterations. Radix sorts iterations are performed recursively. After each iteration, the countdown timer is decreased. Upon the countdown timer reaching zero, one or more comparison sorts is performed on the remainder of the set of data not sorted by the radix sorting.

## Claims

### Claim 1

A method comprising:
receiving, by one or more processors, a set of data to be sorted, wherein the set of data includes a number of tuples;
determining, by one or more processors, a number of iterations of radix sorting to perform on keys of the set of data based, in part, on the number of tuples;
recursively performing, by one or more processors, radix sorting according to the determined number of iterations; and
subsequent to recursively performing radix sorting according to the determined number of iterations, performing, by one or more processors, one or more comparison sorts on a portion of the set of data subsequent to keys of the set of data sorted by the radix sorting.

### Claim 2 (depends on 1)

The method of claim 1, wherein determining the number of iterations of radix sorting to perform on keys of the set of data comprises:
determining, by one or more processors, the number of iterations of radix sorting to perform on keys of the set data based on the logarithm base two of the number of tuples.

### Claim 3 (depends on 1)

The method of claim 1, wherein:
recursively performing radix sorting according to the determined number of iterations includes, at least, generating a plurality of buckets; and
performing the one or more comparison sorts on the portion of the set of data subsequent to the keys of the set of data sorted by the radix sorting comprises performing, by one or more processors, one comparison sort on data within each bucket of the plurality of buckets.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
storing, by one or more processors, a set of information indicating a key after the determined number of iterations of radix sorting.

### Claim 5 (depends on 1)

The method of claim 1, wherein each key is less than or equal to four bytes.

### Claim 6 (depends on 1)

The method of claim 1, further comprising:
setting, by one or more processors, a countdown timer to the number of iterations of radix sorting to perform; and
decreasing, by one or more processors, the countdown timer subsequent to each iteration of radix sorting.

### Claim 7

A computer program product comprising:
a computer readable storage medium and program instructions stored on the computer readable storage medium, the program instructions comprising:
program instructions to receive a set of data to be sorted, wherein the set of data includes a number of tuples;
program instructions to determine a number of iterations of radix sorting to perform on keys of the set of data based, in part, on the number of tuples;
program instructions to recursively perform radix sorting according to the determined number of iterations; and
subsequent to recursively performing radix sorting according to the determined number of iterations, program instructions to perform one or more comparison sorts on a portion of the set of data subsequent to keys of the set of data sorted by the radix sorting.

### Claim 8 (depends on 7)

The computer program product of claim 7, wherein determining the number of iterations of radix sorting to perform on keys of the set of data comprises:
program instructions to determine the number of iterations of radix sorting to perform on keys of the set data based on the logarithm base two of the number of tuples.

### Claim 9 (depends on 7)

The computer program product of claim 7, wherein:
program instructions to recursively perform radix sorting according to the determined number of iterations includes, at least, program instructions to generate a plurality of buckets; and
program instructions to perform the one or more comparison sorts on the portion of the set of data subsequent to the keys of the set of data sorted by the radix sorting comprises program instructions to perform one comparison sort on data within each bucket of the plurality of buckets.

### Claim 10 (depends on 7)

The computer program product of claim 7, further comprising:
program instructions to store a set of information indicating a key after the determined number of iterations of radix sorting.

### Claim 11 (depends on 7)

The computer program product of claim 7, wherein each key is less than or equal to four bytes.

### Claim 12 (depends on 7)

The computer program product of claim 7, further comprising:
program instructions to set a countdown timer to the number of iterations of radix sorting to perform; and
program instructions to decrease the countdown timer subsequent to each iteration of radix sorting.

### Claim 13

A computer system comprising:
one or more computer processors;
one or more computer readable storage media;
program instructions stored on the one or more computer readable storage media for execution by at least one of the one or more processors, the program instructions comprising:
a computer readable storage medium and program instructions stored on the computer readable storage medium, the program instructions comprising:
program instructions to receive a set of data to be sorted, wherein the set of data includes a number of tuples;
program instructions to determine a number of iterations of radix sorting to perform on keys of the set of data based, in part, on the number of tuples;
program instructions to recursively perform radix sorting according to the determined number of iterations; and
subsequent to recursively performing radix sorting according to the determined number of iterations, program instructions to perform one or more comparison sorts on a portion of the set of data subsequent to keys of the set of data sorted by the radix sorting.

### Claim 14 (depends on 13)

The computer system of claim 13, wherein determining the number of iterations of radix sorting to perform on keys of the set of data comprises:
program instructions to determine the number of iterations of radix sorting to perform on keys of the set data based on the logarithm base two of the number of tuples.

### Claim 15 (depends on 13)

The computer system of claim 13, wherein:
program instructions to recursively perform radix sorting according to the determined number of iterations includes, at least, program instructions to generate a plurality of buckets; and
program instructions to perform the one or more comparison sorts on the portion of the set of data subsequent to the keys of the set of data sorted by the radix sorting comprises program instructions to perform one comparison sort on data within each bucket of the plurality of buckets.

### Claim 16 (depends on 13)

The computer system of claim 13, further comprising:
program instructions to store a set of information indicating a key after the determined number of iterations of radix sorting.

### Claim 17 (depends on 13)

The computer system of claim 13, wherein each key is less than or equal to four bytes.

### Claim 18 (depends on 13)

The computer system of claim 13, further comprising:
program instructions to set a countdown timer to the number of iterations of radix sorting to perform; and
program instructions to decrease the countdown timer subsequent to each iteration of radix sorting.