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

2004-12-14

2008-12-16

Mofiz, Apu (Department: 2161)

Data processing: database and file management or data structures

Database design

Data structure types

C712S008000, C712S300000

Reexamination Certificate

active

07467138

ABSTRACT:
A method and associated algorithm for in-place sorting S sequences of binary bits stored contiguously in an array within a memory device of a computer system prior to the sorting. Each sequence includes contiguous fields of bits. The algorithm is executed by a processor of a 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: 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.
Arne Anderson,“Sorting in Linear Time?”, Department of Computer Science, Lund University, Sweden, AMC, 1995.
Arne Anderson,“A New Efficient Radix Sort”, Department of Computer Science, Lund Univisity, Sweden, AMC, 1994.
Maus, Arne, “ARL, a faster in-place, cache friendly sorting algorithm”, in NIK'2002—Norsk Informatikkonferanse, p. 85-95.

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-4028435