/* 
*  Paper COMPSCI 220 --------- Java programs
*  Sorting methods: insertionSort, shellSort, 
*             mergeSort, quickSort, heapSort
*  a[] - an integer array to be sorted
*/ 

public class SortMeth { 

  // Threshold for quickSort
  static public int CUTOFF = 10; 
  
  //-------------------------------------------
  //  insertion sort algorithm
  //-------------------------------------------

  public static void insertionSort(int [] a) { 
    int i, tempi, k; 
 
    for( i = 1; i < a.length; i++ ) { 
      tempi = a[i]; 
      k = i - 1; 
      while( k >= 0 && tempi < a[k] ) { 
	a[k+1] = a[k]; 
	k--; 
      } 
      a[k+1] = tempi; 
    } 
  } 
 
  //-------------------------------------------
  //  Shell's sort algorithm
  //-------------------------------------------

  public static void shellSort(int [] a) { 
    int i, tempi, k, gap; 
 
    for(gap = a.length/2; gap > 0; 
        gap = (gap == 2)? 1 : (int)(gap/2.2) ) 
      for(i = gap; i < a.length; i++) { 
	tempi = a[i]; 
	k = i; 
	while( k >= gap && tempi < a[k-gap]) { 
	  a[k] = a[k-gap]; 
	  k -= gap; 
	} 
	a[k] = tempi; 
      } 
  } 
 
  //-------------------------------------------
  //  mergesort algorithm
  //-------------------------------------------

 
  public static void mergeSort( int [] a) { 
    int []tmpArray = new int[ a.length ]; 
    mergeSort( a, tmpArray, 0, a.length - 1 ); 
  } 
 
  private static void  mergeSort( int [] a,   
                           int [] tmpArray,   
                       int left,  int right ) { 
    if ( left < right ) { 
      int centre = (left + right) / 2; 
      mergeSort( a, tmpArray, left, centre); 
      mergeSort( a, tmpArray, centre + 1, right); 
      merge( a, tmpArray, left, centre + 1, right ); 
    } 
  } 
 
  private static void merge( int [] a,  
                         int [] tmpArray,   
                         int leftPos,  int rightPos, 
                         int rightEnd ) { 
    int leftEnd = rightPos - 1; 
    int tmpPos = leftPos; 
    int leftBeg = leftPos; 
     
    // Main loop 
    while( leftPos <= leftEnd && rightPos <= rightEnd ) 
      if ( a[ leftPos ] < a[ rightPos ] )  
        tmpArray[ tmpPos++ ] = a[ leftPos++ ]; 
      else 
        tmpArray[ tmpPos++ ] = a[ rightPos++ ]; 
 
    // Copy the rest of the first half 
    while( leftPos <= leftEnd ) 
      tmpArray[ tmpPos++ ] = a[ leftPos++ ];      
 
    // Copy the rest of the second half 
    while( rightPos <= rightEnd ) 
      tmpArray[ tmpPos++ ] = a[ rightPos++ ]; 
 
    // Copy tmpArray back 
    for( tmpPos=leftBeg; tmpPos<=rightEnd; tmpPos++ ) 
      a[ tmpPos ] = tmpArray[ tmpPos ]; 
  } 
 
  //-------------------------------------------
  //  quicksort algorithm
  //-------------------------------------------

  private static void quickSort( int  [] a,  
	              int low,   int high) { 
      if( low + CUTOFF > high ) 
		     insertionSort( a, low, high ); 
      else { 
	// Sort low, middle, high 
	int middle = ( low + high ) / 2; 
	if ( a[ middle ] < a[ low ]    ) 
	  swapElements( a, low, middle  ); 
	if ( a[ high ]   < a[ low ]    ) 
	  swapElements( a, low, high    ); 
	if ( a[ high ]   < a[ middle ] ) 
	  swapElements( a, middle, high ); 
 
	// Place pivot at position high - 1 
	swapElements( a, middle, high - 1 ); 
	int pivot = a[ high - 1]; 
 
	// Begin partitioning 
        int i, j; 
	for( i = low, j = high - 1; ; ) { 
	  while( a[ ++i ] < pivot ); 
          while( pivot < a[ --j ] ); 
          if ( i < j ) 
	    swapElements( a, i, j ); 
	  else 
	    break; 
	} 
 
	// Restore pivot 
	swapElements( a, i, high - 1 ); 
 
	quickSort( a, low, i - 1 ); // Sort small elements 
	quickSort( a, i + 1, high ); // Sort large elements 
      } 
  } 
 
  public static void quickSort( int [] a ) { 
    quickSort( a, 0, a.length - 1 ); 
  } 
 
  private static void swapElements( int [] a,  
	                        int i, int j ) { 
    int temp = a[ i ]; 
    a[ i ] = a[ j ]; 
    a[ j ] = temp; 
  } 
 
  private static void insertionSort(int [] a,  
			  int low,  int high) { 
    int i, tempi, k; 
 
    if (low > high || low < 0 || high >= a.length ) { 
       low = 0;
       high = a.length - 1;
    } 
    for( i = low + 1; i <= high; i++) { 
       tempi = a[ i ]; 
       k     = i - 1; 
       while( k >= low && tempi < a[ k ] ) { 
	 a[ k+1 ] = a[ k]; 
	 k--; 
       } 
       a[ k+1 ] = tempi; 
    } 
  } 

  //-------------------------------------------
  //  heapsort algorithm
  //-------------------------------------------

  public static void heapSort( int [] a ) { 
    int index; 
    // build heap 
    for( index = a.length / 2 - 1; index >= 0; 
                                       index-- )
      heapify( a, index, a.length ); 
    // deleteMax 
    for( index = a.length - 1; index >= 1; 
                                       index-- ) { 
      swapElements( a, 0, index );
      heapify( a, 0, index ); 
    } 
  } 
  
  private static void heapify( int [] a, 
                               int index, int size ) { 
    int childPos;  
    int parentPos = index + 1; 
    // position is one more index; 

    for( childPos = parentPos * 2; childPos < size;  
		          childPos = parentPos * 2 ) {	 
      if ( a[ parentPos - 1 ] < a[ childPos - 1 ] || 
		a[ parentPos - 1 ] < a[ childPos ] ) {  
	if ( a[ childPos - 1 ] < a[ childPos] ) { 
	  swapElements( a, parentPos - 1, childPos ); 
	  parentPos = childPos + 1; 
	} 
	else { 
	  swapElements( a, parentPos - 1, childPos - 1 ); 
	  parentPos = childPos; 
        } 
      } 
      else break; 
    } 
    if ( childPos == size && 
        a[ parentPos - 1 ] < a[ childPos - 1 ] ) 
      swapElements( a, parentPos - 1, childPos - 1 ); 
  } 
}