/**
 * Straight insertion sort method
 */
   public static void insSort ( Comparable[] x, int n )
   {  int  lim,    // start of unsorted region
           hole;   // insertion point in sorted region

      for ( lim = 1 ; lim < n ; lim++ )
      {  Comparable save = x[lim];

         for ( hole = lim ;
               hole > 0 && save.compareTo(x[hole-1]) < 0 ;
               hole-- )
         {  x[hole] = x[hole-1];  }

         x[hole] = save;
      } // end for (lim...
   } // end insSort()

/**
 * Optimized insertion sort
 *
 * insertion point is found by binary search
 * data movement in the array is done by System.arraycopy()
 */
   public static void optInsSort ( Comparable[] x, int n )
   {  int  lim,    // start of unsorted region
           hole;   // insertion point in sorted region

      for ( lim = 1 ; lim < n ; lim++ )
      {  Comparable save = x[lim];

         hole = binSearch ( x, lim, save );
         System.arraycopy(x, hole, x, hole+1, lim-hole);

         x[hole] = save;
      } // end for
   } // end optInsSort()

/**
 * Binary search returns point where item IS or BELONGS.
 */
   static int binSearch ( Comparable[] x, int n, Comparable val)
   {  int lo = 0, hi = n-1;

      while (lo < hi)
      {  int mid = (lo + hi) / 2;
         if (val.compareTo(x[mid]) > 0)
            lo = mid + 1;
         else
            hi = mid;
      } // end while
      if ( val.compareTo(x[hi]) > 0 )  // Belongs at the VERY end
         return n;
      else                             // Where val is (or belongs)
         return hi;
   } // end binSearch()

Taken from http://java.sun.com/j2se/1.4/docs/api/java/lang/System.html . . .

arraycopy

public static void arraycopy(Object src,
                             int srcPos,
                             Object dest,
                             int destPos,
                             int length)

Copies an array from the specified source array, beginning at the specified position, to the specified position of the destination array. A subsequence of array components are copied from the source array referenced by src to the destination array referenced by dest. The number of components copied is equal to the length argument. The components at positions srcPos through srcPos+length-1 in the source array are copied into positions destPos through destPos+length-1, respectively, of the destination array.

If the src and dest arguments refer to the same array object, then the copying is performed as if the components at positions srcPos through srcPos+length-1 were first copied to a temporary array with length components and then the contents of the temporary array were copied into positions destPos through destPos+length-1 of the destination array.

If dest is null, then a NullPointerException is thrown.

If src is null, then a NullPointerException is thrown and the destination array is not modified.

Otherwise, if any of the following is true, an ArrayStoreException is thrown and the destination is not modified:

• The src argument refers to an object that is not an array.
• The dest argument refers to an object that is not an array.
• The src argument and dest argument refer to arrays whose component types are different primitive types.
• The src argument refers to an array with a primitive component type and the dest argument refers to an array with a reference component type.
• The src argument refers to an array with a reference component type and the dest argument refers to an array with a primitive component type.

[Remainder of the documentation on arraycopy is omitted]