Browse Prior Art Database

In-Place Reordering of Data using a Double Buffer

IP.com Disclosure Number: IPCOM000104324D
Original Publication Date: 1993-Apr-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 4 page(s) / 94K

Publishing Venue

IBM

Related People

Robinson, JT: AUTHOR

Abstract

Disclosed is a method for in-place reordering of N records residing in main memory using a two record buffer. This method requires 2(N-1) record moves, whereas 3(N-1) record moves are required by the straightforward method using exchanges and a single record buffer.

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

In-Place Reordering of Data using a Double Buffer

      Disclosed  is  a method for in-place reordering of N records
residing in main memory using a two  record  buffer.  This method
requires  2(N-1) record moves, whereas 3(N-1) record moves are
required by the straightforward method using exchanges and a single
record buffer.

      Consider  the problem of reordering a collection of records
residing in main memory (or more generally any  random access
memory),  for  example, in order to sort the records, merge two or
more ordered subsets of the records, etc. Furthermore, assume that it
is necessary, due to (1)  the  size and number of records and (2)
available memory space, to re-order the records in-place, i.e., move
records from one ex- isting  record  location  to  another  using
only  a  small additional amount of memory.

      In  the case of sorting, various in-place methods (such as
bubblesort, quicksort, etc.) are well-known.  However, these
algorithms are generally described in terms of moving or exchanging
records.  In practice, if  records  are  large (say, for example 80
bytes long), it is far better to sort an array  of  pointers  to
records,  moving or exchanging only pointers (which could be, for
example,  two  or  four  bytes long).  After the array of pointers is
sorted, the desired ordering of the records is known, it remains only
to put them in order.  If sufficient memory is available, all records
can  be moved, in order, to a new location, using one move per
record.  The techniques of sorting (or  merging etc.) pointers rather
than records and then moving records to new locations in order are
well-known in practice,  being simply an application of a single
level of indirection.

      If sufficient memory is not available to move every record to a
new location, the records have to be reordered in place.  A
straightforward way to do this is via exchanges us...