US 2009/0276428 A1 · SORTING METHOD AND ALGORITHM CALLED HIGH SPEED SORT

Abstract

In the field of computer-based data processing, data sorting is an important issue. Among various sorting methods, Quick Sort is generally used. However, there is a problem that using Quick Sort makes sort time longer if the data to be sorted is already partially or fully in order. The invention solves the above-mentioned problem and makes the complexity of the sorting lower than or at least equal to that of Quick Sort. Thus, it provides a faster sorting method than Quick Sort does. In a method or program of the invention, ‘long sequence’ being defined as a longest monotonously increasing or monotonously decreasing sequence found in N sequence, a ‘smaller values’ being defined as a sequence of data values smaller than a minimum value among the ‘long sequence’, a ‘larger values’ being defined as a sequence of data values larger than a maximum value among the ‘long sequence’, and a ‘between values’ being defined as values which are larger than the minimum value among the ‘long sequence’ and smaller than the maximum value among the ‘long sequence’ other than the ‘long sequence’. The ‘long sequence’ is already sorted, other three sequences(smaller values, larger values, and between values) is to be internally sorted. Then, the four sequences are merged. Above-mentioned internal sorting uses the method of the invention recursively.

Claims14

Dependent claims

A method, comprising executing an algorithm by a processor of a computer system, said executing said algorithm comprising sorting N sequences of binary bits in ascending or descending order of a value associated with each sequence, said N sequences being stored in a memory device of the computer system prior to said sorting, N being at least 2, said sorting comprising executing program code at nodes of linked execution structure, said executing program code being performed in a sequential order with respect to said nodes, said executing program code including:

a) finding a longest sequence among monotonously increasing or monotonously decreasing sequences which are from N sequences;
b) dividing said N sequences into four portions, the four portions being a long sequence, a smaller values, a larger values, and a between values, said long sequence being defined as a sequence found in step a), said smaller values being defined as a sequence of data values smaller than a minimum value among said long sequence, said larger values being defined as a sequence of data values larger than a maximum value among said long sequence, and said between values being defined as values which are larger than said minimum value among said long sequence and smaller than said maximum value among said long sequence other than said long sequence;
c) internally sorting each of said smaller values, said larger values, and said between values;
and
d) merging said long sequence, said smaller values, said larger values, and between values.

2 more elements

A computer program product, comprising:

A computer usable medium having a computer program embodied therein, said computer readable program comprising an algorithm for Sorting N sequences of binary bits in ascending or descending order of a value associated with each sequence, said N sequences being stored in a memory device of the computer system prior to said sorting, N being at least 2, said sorting comprising executing program code at nodes of linked execution structure, said executing program code being performed in a sequential order with respect to said nodes, said executing program code including:
a) finding a longest sequence among monotonously increasing or monotonously decreasing sequences which are from N sequences;
b) dividing said N sequences into four portions, the four portions being a long sequence, a smaller values, a larger values, and a between values, said long sequence being defined as a sequence found in step a), said smaller values being defined as a sequence of data values smaller than a minimum value among said long sequence, said larger values being defined as a sequence of data values larger than a maximum value among said long sequence, and said between values being defined as values which are larger than said minimum value among said long sequence and smaller than said maximum value among said long sequence other than said long sequence;
c) internally sorting each of said smaller values, said larger values, and said between values;
and
d) merging said long sequence, said smaller values, said larger values, and between values.

3 more elements

Dependencies are inferred from the claim text.

Sorting method and algorithm called high speed sort

Life of this patent

Sorting method and algorithm called high speed sort

Life of this patent

Abstract

Claims14