Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Average-Case O(n) Complexity Sorting Algorithm

IP.com Disclosure Number: IPCOM000117814D
Original Publication Date: 1996-Jun-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 4 page(s) / 85K

Publishing Venue

IBM

Related People

Lin, ZJ: AUTHOR [+4]

Abstract

Disclosed is an efficient sorting algorithm. The method is based on splitting the keys into groups and using the key values to index a reconfigurable data structure. This algorithm exhibits O(n) complexity under user control.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 50% of the total text.

Average-Case O(n) Complexity Sorting Algorithm

      Disclosed is an efficient sorting algorithm.  The method is
based on splitting the keys into groups and using the key values to
index a reconfigurable data structure.  This algorithm exhibits O(n)
complexity under user control.

      The proposed invention provides an innovative self-sorting data
structure which can be used to sort large groups of data without
doing data comparison and with efficient use of memory.  Although,
sorting based on key computation (a.k.a., radix sort or linear sort)
requires linear (n) run-time, the actual implementation depends on
the size of the data group and the data pattern.  The sorting
mechanism based on self-sorting data structure described here,
however, requires linear (n) run-time and is significantly simpler to
implement since the data structure is dynamically constructed and
does not require any knowledge of data pattern in advance.

      This disclosure presents a data-structure for sorting a group
of n items without doing any data comparison.  Suppose, the first
item is X.  An algorithm is devised to divide it's binary
representation, e.g., 0x10101...1010, to m key groups.  Then, there
will be k0 .. km keys for X; each of the keys can have bkm bits, for
2**bkm different values respectively.  Allocate an integer pointer
array of size 2**bk0 with initial value being null.  The key k0 is
then used as an index to get to the array element.  This element is
initialized and pointed to the newly created integer pointer array of
size 2**bk1.  In this array, k1th element is then initialized and
pointed to a newly created integer pointer array of size 2**bk2, so
on and so forth, until the array for key km. is reached, which is
initialized as an array of integer.

      For the rest of the items in the group, the same algorithm is
used to place them, except when an array element is already
initialized.  In the case where an existing pointer is found, it just
means there are items in the group with the same significant keys.

It is not necessary to create an array for this key and array km's
element Im is incremented by one.  If the next keys are still the
same as others', traverse along the pointer, otherwise, a null
pointer or integer value 0 is hit.  The previously described
procedure is repeated.  The principal idea is that the keys
themselves are used to index the different arrays and the contents of
the arrays are pointers to subsequent arrays.  Each integer value of
the last array in the array chain indicates the number of items with
same binary representation.  The algorithm and graph for inserting
the entries are given below.
  void insert_entry(int *table_store, /* complete storage for all
                                          entries, actually an
integer
                                          pointer of size k0 */
       ...