Algorithm for sorting bit sequences in linear complexity

Details Algorithm for sorting bit sequences in linear complexity Algorithm for sorting bit sequences in linear complexity

2011-08-30

2011-08-30

Mofiz, Apu M (Department: 2161)

Data processing: database and file management or data structures

Database and file access

Preparing data for information retrieval

C707S736000

Reexamination Certificate

active

08010540

ABSTRACT:
A computer program product and computer system for in-place sorting sequences of binary bits stored contiguously in an array within a memory device of the computer system prior to sorting. Each sequence includes contiguous fields of bits. The algorithm is executed by a processor of the computer system. The in-place sorting executes program code at each node of a linked execution structure. Each node includes a segment of the array. The program code is executed in a hierarchical sequence with respect to the nodes. Executing program code at each node includes: dividing the segment of the node into groups of sequences based on a mask field having a mask width, wherein each group has a unique mask value of the mask field; and in-place rearranging the sequences in the segment, wherein the rearranging results in each group including only those sequences having the unique mask value of the group.

REFERENCES:
patent: 3815038 (1974-06-01), Davis
patent: 4809158 (1989-02-01), McCauley
patent: 5440734 (1995-08-01), Wagar
patent: 5546390 (1996-08-01), Stone
patent: 5560007 (1996-09-01), Thai
patent: 5671406 (1997-09-01), Lubbers et al.
patent: 5680607 (1997-10-01), Brueckheimer
patent: 5799184 (1998-08-01), Fulton et al.
patent: 5873078 (1999-02-01), Angle et al.
patent: 5924091 (1999-07-01), Burkhard
patent: 6128614 (2000-10-01), Mennemeier et al.
patent: 6144986 (2000-11-01), Silver
patent: 6373012 (2002-04-01), Crutchfield et al.
patent: 6381605 (2002-04-01), Kothuri et al.
patent: 6397216 (2002-05-01), Cattanach et al.
patent: 6519593 (2003-02-01), Matias et al.
patent: 6532457 (2003-03-01), Tal et al.
patent: 6553370 (2003-04-01), Andreev et al.
patent: 6564211 (2003-05-01), Andreev et al.
patent: 6571244 (2003-05-01), Larson
patent: 2002/0032681 (2002-03-01), Feldmeier et al.
patent: 2002/0143747 (2002-10-01), Tal et al.
patent: 2002/0165707 (2002-11-01), Call
patent: 2002/0174130 (2002-11-01), Wagner
patent: 2003/0004938 (2003-01-01), Lawder
patent: 2003/0051020 (2003-03-01), Kadam et al.
patent: 2003/0093565 (2003-05-01), Berger et al.
patent: 2003/0130981 (2003-07-01), Nehru et al.
patent: 2004/0032681 (2004-02-01), Smith et al.
Office Action (Mail Date Feb. 25, 2010) for U.S. Appl. No. 11/970,600, filed Jan. 8, 2008; Confirmation No. 3403.
Notice of Allowance (Mail Date Sep. 7, 2010) for U.S. Appl. No. 11/968,266, filed Jan. 2, 2008; Confirmation No. 8631.
Office Action (Mail Date Apr. 21, 2010) for U.S. Appl. No. 11/968,266, filed Jan. 2, 2008; Confirmation No. 8631.
Notice of Allowance (Mail Date Apr. 29, 2010) for U.S. Appl. No. 11/970,600, filed Jan. 8, 2008; Confirmation No. 3403.
Maus, Arne; Arl, a faster-in-place, cache friendly sorting algorithm; in NIK'2002—Norsk Informatikkonferanse, pp. 85-95.
Andersson, Arne et al; Sorting in Linear Time?; Department of Computer Science, Lund University, Sweden, AMC, 1995; pp. 427-436.
Andersson, Arne et al.; A New Efficient Radix Sort; Department of Computer Science, Lund University, Sweden, AMC, 1994; 8 pages.
Notice of Allowance (mail date Nov. 12, 2008) for U.S. Appl. No. 11/473,288, filed Jun. 22, 2006; First Named Inventor Dennis J. Carroll; Confirmation No. 6602; Customer No. 30449.
Notice of Allowance (mail date Aug. 11, 2008) and Supplemental Notice of Allowability (mail date Nov. 18, 2008) for U.S. Appl. No. 11/011,930, filed Dec. 14, 2004; First Named Inventor Dennis J. Carroll; Confirmation No. 9521; Customer No. 30449.

Affiliated with

Also associated with

Rating

Algorithm for sorting bit sequences in linear complexity does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Algorithm for sorting bit sequences in linear complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithm for sorting bit sequences in linear complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2793911