US 2017/0286459 A1 · INCREASING RADIX SORTING EFFICIENCY UTILIZING A CROSSOVER POINT

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.

Claims18

Dependent claims

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.

2 more elements

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.

6 more elements

Dependencies are inferred from the claim text.

Facts

Application

15/084,626Filed 30 Mar 2016

Published

5 Oct 2017

Term ends

Not estimatedThe source records don’t support an estimate.

Classification6 codes

G06F 7/24
Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc: sorting, i.e. extracting data from one or…
G06F 7/36
Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc: combined merging and sorting
G06F 16/217
Design, administration or maintenance of databases: database tuning
G06F 16/22
Of structured data, e.g. relational data: indexing; Data structures therefor; Storage structures

Increasing radix sorting efficiency utilizing a crossover point

Life of this patent

Increasing radix sorting efficiency utilizing a crossover point

Life of this patent

Abstract

Claims18