public class aufgabe43 {
    
    static void printfeld (Comparable[] feld)
    {
        for (int i = 0; i < feld.length; i++)
            System.out.print (feld[i] + " ");
        System.out.println ();
    }
    
    static void swap (Comparable[] feld, int idx1, int idx2)
    {
        Comparable temp = feld[idx1];
        feld[idx1] = feld[idx2];
        feld[idx2] = temp;
    }
    
    static void msort (Comparable[] feld, int l, int r)
    {
        int i, j, k;
        Comparable[] b = new Comparable[feld.length];
        
        if (r > l) {
            // zu sortierendes Feld teilen
            int mid = (r + l) / 2;
            // Teilfelder sortieren
            msort (feld, l, mid);
            msort (feld, mid + 1, r);
            
            // Ergebnisse mischen über Hilfsfeld b
            for (i = mid + 1; i > l; i--)
                b[i - 1] = feld[i - 1];
            
            for (j = mid; j < r; j++)
                b[r + mid - j] = feld[j + 1];
            
            for (k = l; k <= r; k++) {
                if (b[i].compareTo(b[j])<0)
                    feld[k] = b[i++];
                
                else
                    feld[k] = b[j--];
            }
        }
    }
    
    static void mergeSort (Comparable[] feld) {
        msort (feld, 0, feld.length - 1);
    }
    
    public static void main(String[] args) {
        
        Comparable[] feldInt = {new Integer(22), new Integer(6), new Integer(2), new Integer(10), new Integer(50), new Integer(12)};
        printfeld(feldInt);
        mergeSort(feldInt);
        printfeld(feldInt);
        
        Comparable[] feldchar = {new Character('l'), new Character('n'),new Character('b'),new Character('z'),new Character('d')};
        printfeld(feldchar);
        mergeSort(feldchar);
        printfeld(feldchar);
    }
}