Interpolation Search, counting sort, bottom up merge sort, heap sort (main loop),

ImprovementsOnMethods.java

public class ImprovementsOnMethods{

  /*
  INTERPOLATION SEARCH - improvement on binary search
  searches for closer values than always choosing mid values 
  Time : O(loglogn) - for sorted and uniformly distributed arrays 
  */
  
  int interpolationSearch(int[] A, int key){
      int lo=0,hi=A.length-1;
      while(lo<=hi){
          int pos = lo+ [(key-A[lo])*(hi-lo)/(A[hi]-A[lo])];
          int cmp = A[pos]-key;
          if(cmp>0) hi = pos-1;
          else if(cmp<0) lo = pos+1;
          else return pos;
      }  
      return -1;
  }
  
  /*
  COUNTING SORT - implementation 
  intput- A[] , output - out[], range - [1-n]
  auxillary count - C[]
  */
  
  int[] countingSort(A[], int lo, int hi){
      
      int[] count = new int[hi-lo+1];
      for(int i=0; i<A.length; i++){
          count[A[i]]++;
      }
      
      for(int i=1; i<A.length; i++){
          count[i]+= count[i-1];
      }
      
      int[] out = new int[A.length];    
      for(int i=0; i<A.length; i++){
          out[--count[A[i]]] = A[i];
      }
      return out;
  
  }
  
  /*
  RADIX SORT - implementation
  intput- A[n] , output - out[], range - [1-n^2]
  auxillary count - C[]
  */
  
  
  
  
  
  /*
  BOTTOM UP - Merge Sort
  */
  int[] crude2 = new int[N];
  
  public static void merge(int[] ar, int lo, int mid, int hi){		
		for(int i=0;i<ar.length;i++){ crude2[i]=ar[i];}
		int j = mid+1,i=lo;
		for(int p=lo;p<=hi;p++){
			if(i>mid) {ar[p]= crude2[j++]; }
			else if(j>hi){ ar[p]= crude2[i++];}
			else if(crude2[i]<crude2[j]){ ar[p] = crude2[i++];}
			else {ar[p]= crude2[j++];}
		}
		
	}
	
	
	public static void sortbu(int[] ar){
		int N = ar.length;
		for(int sz=1;sz<N;sz=sz+sz){
			for(int lo=0;lo<N-sz;lo=lo+sz+sz){
				merge(ar,lo,lo+sz-1, Math.min(lo+sz+sz-1, N-1));
			}
		}
	}
  
  
  /*
  MAIN PART OF HEAP SORT
  */
  sort(){
    for(int i=N/2;i>=1;i--){
			ob.sink(i,N,ar);
		}
		while(N>1){
			ob.exch(1,N--,ar);
			ob.sink(1, N, ar);			
		}
  } 

}