class Sorter{

    static boolean isSorted(char[] a, int lo, int hi){
		    for (int k= lo; k<hi; k++) if (a[k]> a[k+1]) return false;
		    return true;
	      }

    static boolean isSorted(char[] a){
		    return isSorted(a, 0, a.length-1);
	      }
    
    
    private final static void swap(char[] a, int i, int k){
			char temp = a[i];
			a[i] = a[k];
			a[k] = temp;
			}

    static void bubbleSort1(char[] a){
			int hi = a.length-1; 
			for (int k = hi; k > 0; k--)
				for (int i = 0; i < k; i++)
					if ( a[i] > a[i+1]) swap (a, i, i+1);
			}
       
    static void bubbleSort2(char[] a){
				int hi = a.length-1; 
				for (int k = hi; k > 0; k--){
					boolean test = true;
					for (int i = 0; i < k; i++)
						if ( a[i] > a[i+1]) { swap (a, i, i+1); test = false;}
					if (test) break;
					//System.out.println(k); 
					}
			}
 
   static void bubbleSort3(char[] a){
		int hi = a.length-1; 
		int k = hi;
		while ( k > 0 ){
			int maxSwap = 0;
			for (int i = 0; i < k; i++)
				if ( a[i] > a[i+1]) { swap (a, i, i+1); maxSwap = i;}
			k = maxSwap; 
			//System.out.println(k); 
			}
	}
       
    private static int minPos(char[] a, int lo, int hi){
			int min = lo;
			for (int i = lo+1; i <= hi; i++) if (a[i] < a[min]) min = i;
			return min;
			} 

    static void selectionSort(char[] a){
			int hi = a.length-1;
			for (int k = 0; k < hi; k++){
				int min = minPos(a, k, hi);
				if ( min != k) swap (a, min, k); 
				}
			} 
    
    
     static void insertionSort(char[] a){
			int hi = a.length-1;
			for (int k = 1; k <= hi; k++)
				if (a[k] < a[k-1]){
					char x = a[k]; 
					int i;
					for ( i = k; ( (i > 0) && (a[i-1] > x) ) ;  i-- ) 
						a[i] = a[i-1];
					a[i] = x;
					}
			} 

       
     static void shellSort(char[] a){
				int hi = a.length-1;
				int hmax=1, h ;
				for ( hmax=1; hmax < hi ; hmax = 3*hmax+1 ){ };
				for ( h = hmax/3; h > 0; h /= 3) 
			           for (int k = h; k <= hi; k++)
					if(a[k] < a[k-h]){
						char x = a[k]; 
						int i;
						for ( i = k; ( (i > (h-1)) && (a[i-h] > x) ) ;  i-=h )
							a[i] = a[i-h];
						a[i] = x;
						}

       } 
       
     static void quickSort(char[] a){
			int hi = a.length-1;
			rekQuickSort(a, 0, hi);
			}
		
		 static void rekQuickSort(char[] a, int lo, int hi){
			int li  = lo; 
			int re  = hi; 
			int mid = (li+re)/2;
			if (a[li]  > a[mid]) swap(a, li, mid);
			if (a[mid] > a[re])  swap(a, mid, re);
			if (a[li]  > a[mid]) swap(a, li, mid);
			// <= 3 Elemente haben wir schon sortiert ! 
		  //  > 3 Elemente müssen noch sortiert werden ! 
			if ((re - li) > 2){
				char w = a[mid];
				do{
						while (a[li] < w) li++;
						while (w < a[re]) re--;
						if (li <= re){ swap(a, li, re); li++; re--;}
					}while (li <= re);
				if (lo < re) rekQuickSort(a, lo, re); 
				if (li < hi) rekQuickSort(a, li, hi); 
				}
	}
	
	static void quickSort2(char[] a){
			int hi = a.length-1;
			rekQuickSort2(a, 0, hi);
			}
		
		 static void rekQuickSort2(char[] a, int lo, int hi){
			int li  = lo; 
			int re  = hi; 
			int mid = (li+re)/2;
			if (a[li]  > a[mid]) swap(a, li, mid);
			if (a[mid] > a[re])  swap(a, mid, re);
			if (a[li]  > a[mid]) swap(a, li, mid);
			// <= 3 Elemente haben wir schon sortiert ! 
		  //  > 3 Elemente müssen noch sortiert werden ! 
			if ((re - li) > 2){
				char pivot = a[mid];
				swap(a, mid, re);
				int k = li;
				for (int i= li; i < hi; i++){
					if (a[i] < pivot){swap(a,i,k);k++;}
				}
				swap(a,k,re);
				re = k-1;
				li = k+1;
				if (lo < re) rekQuickSort2(a, lo, re); 
				if (li < hi) rekQuickSort2(a, li, hi); 
				}
	}
       
       
     static void mergeSort1(char[] a){
       int hi = a.length-1;
       RekMergeSort(a, 0, hi);
       }
       
     static void RekMergeSort(char[] a, int lo, int hi){
       if (lo < hi){
          int mid = (lo + hi +1)/2;
          RekMergeSort(a, lo, mid-1);
          RekMergeSort(a, mid, hi);
          int len = hi-lo+1;
					char [] temp = new char[len];
					for (int k=0, li=lo, re=mid; k < len; k++)
						if ((li < mid) && ((re > hi) ||(a[li] < a[re]))) // links gewinnt
							temp[k] = a[li++];
						else
							temp[k] = a[re++]; 
					//for (int i=0; i < len; i++) a[lo+i] = temp[i]; 
					System.arraycopy(temp,0,a,lo,len);
          }
       } 
     
     static void mergeSort2(char[] a){
       int hi = a.length-1;
       mSort(a, 0, hi);
       }

     static void mSort(char[] a, int lo, int hi){
				if (lo < hi){int mid=(lo+hi+1)/2;
					mSort(a, lo, mid-1);
					mSort(a, mid, hi);
					merge(a,lo,mid,hi);
				}
	}  
	
    static void merge(char[] a, int lo, int mid, int hi){
			int len = hi-lo+1;
			char [] temp = new char[len];
			for (int k=0, li=lo, re=mid; k < len; k++)
				if ((li < mid) && ((re > hi) ||(a[li] < a[re]))) // links gewinnt
					temp[k] = a[li++];
				else
					temp[k] = a[re++]; 
			//for (int i=0; i < len; i++) a[lo+i] = temp[i]; 
			System.arraycopy(temp,0,a,lo,len);
	} 
       
     static char[] upHeapBuch(char[] ap, char ext){
				int l = ap.length + 1;
				char[] a= new char[l];
				System.arraycopy(ap, 0, a, 0, l-1);
				int i = l-1;
				a[i] = ext;
				while (i > 0){
					int ni = (i-1)/2;
					if (a[i] > a[ni]){
						swap(a, i, ni);
						i = ni;
						}
					else break;
					}
				return a;
		}
		
	static char[] downHeapBuch(char[] ap){
		int l = ap.length - 1;
		char[] a = new char[l];
		System.arraycopy(ap, 1, a, 1, l-1);
		a[0] = ap[l];
		int i = 0;
		int ni = 1;
		while (ni < l){
			// Linker oder rechter Zweig
			if (((ni+1) < l) && (a[ni] < a[ni+1])) ni++; 
			if (a[i] < a[ni]){ // tauschen ?
				swap(a, i, ni);
				i = ni;
				ni += ni + 1;
				}
			else break;
		}
		return a;
	} 
     
     static void downHeap(char[] a, int i, int m){
       int sonny = 2*i + 1;
       while (sonny <= m){
         if ((sonny < m) && (a[sonny] < a[sonny+1])) sonny++; // Linker oder rechter Zweig
         if (a[i] < a[sonny]) { // tauschen ?
            swap(a, i, sonny); 
            i = sonny; 
            sonny += sonny + 1;
            } 
         else break;
         }
       }  
       
     static void heapSort(char[] a){
       int hi = a.length-1;
       for (int i = hi/2; i >= 0; i--) downHeap(a, i, hi); 
       for (int i = hi; i > 0; i--) { swap(a, i, 0); downHeap(a, 0, i-1);}
       }
       
     static void distributionSort1(char[] a){
       int hi = a.length-1;
       char[] b = new char[hi+1];
       int[] count = new int[256];
       
       for (int i=0; i <= hi; i++) // Zählen
          count[ a[i] ]++;
       for (int i=1; i < 256; i++) // Aufsummieren
          count[i] += count[i-1];
       for (int i = hi; i >= 0; i--) // Verteilen
		  b[--count[a[i]]] = a[i];
	   //for (int i=0; i <= hi; i++) a[i] = B[i];	
	   System.arraycopy(b, 0, a, 0, hi+1);
       }  

     static void distributionSort2(char[] a){
     	 	int hi = a.length;
			//for (int k = n; k > 0; k--){ // für jede Schlüsselposition
				int[] count = new int[256];
				
				for (int i=0; i < hi; i++) // Bedarf fuer die
					count[ a[i] ]++;       // Fachgroesse bestimmen
				for (int z=1; z < 256; z++)   // Aufsummieren
					count[z] += count[z-1]; 
				for (int z=255; z > 0; z--) // Beginn der Fächer bestimmen
					count[z] = count[z-1];  // Fach fuer Zeichen z beginnt
				count[0]=0;		                // jetzt an Position count[z]
				char[] b = new char[hi];
				for (int i = 0; i < hi ; i++){ // Einordnen,
					int z = a[i];	                // dabei Fachgrenze
					b[count[z]++]= a[i];             // anpassen
			}
		System.arraycopy(b, 0, a, 0, hi); // Zurückkopieren
	//} 
}

     

}