Browse Prior Art Database

Sorting Algorithm

IP.com Disclosure Number: IPCOM000121269D
Original Publication Date: 1991-Aug-01
Included in the Prior Art Database: 2005-Apr-03
Document File: 4 page(s) / 114K

Publishing Venue

IBM

Related People

Brandon, M: AUTHOR

Abstract

An efficient programming sort algorithm is described in which the sort element is broken down into a hierarchy of sub-strings. The algorithm requires a low storage overhead and has the additional feature that the sorted elements may still be accessed in their original (unsorted) order. The technique will be illustrated below by showing how an array of elements can be sorted. However, it will be clear that the disclosed algorithm is applicable to a list of elements stored in any form. Inputs to the algorithm SORT_ELEMENTS[1..N] This is an array of elements to be sorted. In the present example, the elements are sorted according to an alphanumerical key contained in each element. MAX_USED_ELEMENT This is a variable representing the index of the highest used entry in the SORT_ELEMENTS array.

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

Sorting Algorithm

      An efficient programming sort algorithm is described in
which the sort element is broken down into a hierarchy of
sub-strings.  The algorithm requires a low storage overhead and has
the additional feature that the sorted elements may still be accessed
in their original (unsorted) order.  The technique will be
illustrated below by showing how an array of elements can be sorted.
However, it will be clear that the disclosed algorithm is applicable
to a list of elements stored in any form.
Inputs to the algorithm
SORT_ELEMENTS[1..N]      This is an array of elements to be sorted.
In the present example, the elements are sorted according to an
alphanumerical key contained in each element.
MAX_USED_ELEMENT         This is a variable representing the index of
the highest used entry in the
SORT_ELEMENTS array.  Sorting is performed from the first entry to
the highest used entry.
Outputs after sorting
SORT_ELEMENTS[1..N]      The elements in this array remain in their
original (unsorted) order. However, an extra field, to be referred to
as the SORT_PTR field, is added to this array. This extra field is
filled during the sort process to provide a pointer or index to the
elements in their sorted order.  In other words, to find the nth
element in the sorted order, it is necessary to:
                          (i)   Access the nth element, SORT_ELEMENTS
[n], in the array;
                          (ii)  Extract the value in the SORT_PTR
field for this element - call this extracted value 'y';
                          (iii) Access the yth element, SORT_ELEMENTS
(y), in the array.  This is then the nth element in the sorted order.

      The sorting algorithm will now be explained by way of an
example.  In the example the following array of elements will be
sorted according to the alphanumerical key contained in each element:

      Element                  Alphanumerical Key
SORT_ELEMENTS     (1)                          AX
SORT_ELEMENTS     (2)                          BX
      ..           (3)                          CX
      ..           (4)                          AY
      ..           (5)                          BY
SORT_ELEMENTS     (6)                          BZ

      A first scan through the list of elements is performed. In this
scan the number of occurrences of each possible character in the
leftmost character position of the keys is counted.  Also, an initial
arbitrary value is placed in the SORT_PTR field of each element.
After first scan:

      Element                  SORT_PTR Field
SORT_ELEMENTS      (1)                        ...