         Name: SORT1
         Type: Assembler Macro
      Version: 1.0
 Date Entered: 11-Sept-87
  Last Change: 11-Sept-87

  Description: Sorting an Array by Straight Selection

 SORT1 is a programming example of sorting by "Straight Selection"
 on the DSP56001.  The macro will sort an array of size "N_ITEMS"
 in X memory space starting at location "ARRAY".

 SORT1 uses the straight selection algorithm to sort an ARRAY of
 signed numbers.  The sort is performed "in-place" and requires no
 additional memory locations.  The algorithm searches all items 
 of the array to find the lowest valued item which is swapped with
 the next item of the final sorted sequence [1].
 
 For SORT1 the execution time is proportional to the square of
 the array size (N_ITEMS).  In this DSP56000 implementation the
 execution time for SORT1 is constant for any given array size,
 even if the array is already ordered, inversely ordered or
 randomly ordered when the algorithm is executed.  The benchamarks
 are for randomly ordered arrays.

 The SORT1 macro is efficient for sorting smaller arrays of numbers. 
 SORT2 is more efficient for larger arrays.  
                                 
 Benchmark Performances for 20.5MHz DSP56001:

 Array Size             SORT1                   SORT2
 (N_ITEMS)      (Straight Selection)         (Heapsort)
 ----------     --------------------         ----------
      8                 14.5us                  51.7us
     16                 41.8us                  130us
     32                 134us                   317us
     64                 468us                   741us
    128                 1.7ms                   1.7ms
    256                 6.7ms                   4.0ms
    512                26.1ms                   9.1ms


 References
 ----------
 [1] Niklaus Wirth, "Algorithms + Data Structures = Programs,"
 Prentice-Hall, 1976. pp. 63-65, Program 2.3.

