public class Msort
{
    public int[] index;

    /**es müssen die Anzahl der zu sortierenden Elemente übergeben werden*/
    public Msort(int anzahl)    
    {
        index = new int[anzahl];
    }

    void mergesort(int a[], int low, int high)  
    { 
       if(low == high)  
            return; 
       int length = high-low+1; 
       int pivot = (low+high) / 2; 
       mergesort(a, low, pivot); 
       mergesort(a, pivot+1, high); 
       int working[] = new int[length]; 
       for(int i = 0; i < length; i++)  
           working[i] = a[low+i]; 
       int m1 = 0;  
       int m2 = pivot-low+1; 
       for(int i = 0; i < length; i++) 
       { 
         if(m2 <= high-low)  
             if(m1 <= pivot-low)  
                 if(working[m1] > working[m2])  
                     a[i+low] = working[m2++];   
                 else  
                     a[i+low] = working[m1++]; 
             else  
                 a[i+low] = working[m2++]; 
         else  
             a[i+low] = working[m1++]; 
       } 
     }

    public void nummern(double a[], int low, int high)  
    { 
       if(low == high)  
            return; 
       int length = high-low+1; 
       int pivot = (low+high) / 2; 
       nummern(a, low, pivot); 
       nummern(a, pivot+1, high); 
       double working[] = new double[length]; 
       int iworking[] = new int[length]; 
       for(int i = 0; i < length; i++)
       {  
           working[i]  = a[low+i]; 
           iworking[i] = index[low+i]; 
       }    
       int m1 = 0;  
       int m2 = pivot-low+1; 
       for(int i = 0; i < length; i++) 
       { 
         if(m2 <= high-low)  
         {
             if(m1 <= pivot-low)
             {  
                 if(working[m1] > working[m2])  
                 {
                     a[i+low] = working[m2];   
                     index[i+low] = iworking[m2];   
                     m2++;
                 }    
                 else
                 {  
                     a[i+low] = working[m1]; 
                     index[i+low] = iworking[m1]; 
                     m1++;
                 }    
             }        
             else 
             { 
                 a[i+low] = working[m2]; 
                 index[i+low] = iworking[m2]; 
                 m2++;
             }    
         }        
         else
         {  
             a[i+low] = working[m1]; 
             index[i+low] = iworking[m1];
             m1++; 
         }    
       } 
     }

    public void nummern(int a[], int low, int high)  
    { 
       if(low == high)  
            return; 
       int length = high-low+1; 
       int pivot = (low+high) / 2; 
       nummern(a, low, pivot); 
       nummern(a, pivot+1, high); 
       int working[] = new int[length]; 
       int iworking[] = new int[length]; 
       for(int i = 0; i < length; i++)
       {  
           working[i]  = a[low+i]; 
           iworking[i] = index[low+i]; 
       }    
       int m1 = 0;  
       int m2 = pivot-low+1; 
       for(int i = 0; i < length; i++) 
       { 
         if(m2 <= high-low)  
         {
             if(m1 <= pivot-low)
             {  
                 if(working[m1] > working[m2])  
                 {
                     a[i+low] = working[m2];   
                     index[i+low] = iworking[m2];   
                     m2++;
                 }    
                 else
                 {  
                     a[i+low] = working[m1]; 
                     index[i+low] = iworking[m1]; 
                     m1++;
                 }    
             }        
             else 
             { 
                 a[i+low] = working[m2]; 
                 index[i+low] = iworking[m2]; 
                 m2++;
             }    
         }        
         else
         {  
             a[i+low] = working[m1]; 
             index[i+low] = iworking[m1];
             m1++; 
         }    
       } 
     }


     /**Liefert Indices zu a, so, dass bei a[indices[0..i..n]] die Werte der Größe nach geordnet
     *herauskommen.
     */
    public int[] nummern(double[] a)
    {
//       index = new int[a.length];  //damit nicht immer neu erzeugt wird!!!!
       for(int i=0;i<index.length;i++)
           index[i] = i;
       
       double[] m = new double[a.length];    
           
       for(int i=0;i<m.length;i++)
           m[i] = a[i];    
           
       nummern(m, 0, m.length-1);
       return index;     
    }

    public double[] elemente(double[] a)
    {
       index = new int[a.length];
       for(int i=0;i<index.length;i++)
           index[i] = i;
       
       double[] m = new double[a.length];    
           
       for(int i=0;i<m.length;i++)
           m[i] = a[i];    
           
       nummern(m, 0, m.length-1);
       return m;     
    }

     /**Liefert Indices zu a, so, dass bei a[indices[0..i..n]] die Werte der Größe nach geordnet
     *herauskommen.
     */
     public int[] nummern(int[] a)
     {
        index = new int[a.length];
        for(int i=0;i<index.length;i++)
            index[i] = i;

        int[] m = new int[a.length];    
            
        for(int i=0;i<m.length;i++)
            m[i] = a[i];    
                    
        nummern(m, 0, m.length-1);
        return index;     
     }
     
     public int[] elemente(int[] a)
     {
        index = new int[a.length];
        for(int i=0;i<index.length;i++)
            index[i] = i;

        int[] m = new int[a.length];    
            
        for(int i=0;i<m.length;i++)
            m[i] = a[i];    
                    
        nummern(m, 0, m.length-1);
        return m;     
     }     
 }
