Merge Sort Algorithm

[insanely_sane]

EDIT: This was moved from the Java discussion forum. It seems more appropriate to post it here. This is not exactly a homework assignment. I'm just doing it for fun ^^

Hey guys. I am currently just a 11th grade student but since I'm done the whole curriculum for my Computers class already, I recently just started making extra stuff for fun. One of things I'm doing is Making a graphical/visual sorting applet. Something like : http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html

I have my code for insertion, shaker, bubble and selection sorts. But since I haven't done merge sort yet, I was wondering if anyone could help me out and give me the code.
I use an IDE (Ready to program) with Java version 1.4.2 (If that helps ... )
This is what I have so far:

import java.awt.*;
import java.applet.*;

public class SortAnimator extends Applet
{
    Button select, bubble, insert;
    int size = 50;
    int a[] = new int [size];


    Button reset;

    public void init ()
    {
        resize (900, 900);
        for (int i = 0 ; i < size ; i++)
        {
            if (i == 0)
                a [0] = 10;
            else
                a [i] = a [i - 1] + 10;
        }


        for (int i = 1 ; i <= 1000000 ; i++)
        {
            int index1 = (int) ((Math.random () * (size)));
            int index2 = (int) ((Math.random () * (size)));
            while (index1 == index2)
            {
                index2 = (int) ((Math.random () * (size)));
            }
            int temp = a [index1];
            a [index1] = a [index2];
            a [index2] = temp;
        }
        select = new Button ("selection sort");
        add (select);
        bubble = new Button ("bubble sort");
        add (bubble);
        insert = new Button ("insertion sort");
        add (insert);
        reset = new Button ("Reset array");
        add (reset);


    }


    public boolean action (Event e, Object o)
    {
        if (e.target == select)
        {
            selectionSort (a, size);

        }
        else if (e.target == bubble)
        {
            bubble (a, size);
        }
        else if (e.target == insert)
        {
            insertion (a,size);
        }
        else if (e.target == reset)
        {
            reset ();
        }
        return true;
    }


    public void paint (Graphics g)
    {

        printarray (a, size);
    }


    public void printarray (int a[], int size)
    {
        Graphics g = getGraphics ();
        g.setColor (Color.white);
        g.fillRect (25, 25, 1000, 1000);
        
        int x = 50;
        for (int i = 0 ; i < size ; i++)
        {
            g.setColor (new Color (0,100+a[i]/4,0));
            g.fillRect (x, 50, 10, a[i]);
            x += 12;
            
        }

    }

    //Selection Sort
    public void selectionSort (int a[], int size)
        //Pre: 0 <= size <= number of elements in the array
        //Post: values in a [0..size-1] are in ascending order
    {
        int numUnsorted = size;
        int index; //general index
        int max; //index of largest value
        int temp;

        while (numUnsorted > 0)
        {
            //determine maximum value in array
            max = 0;
            for (index = 0 ; index < numUnsorted ; index++)
            {
                if (a [max] < a [index])
                    max = index;

            }
            temp = a [max];
            a [max] = a [numUnsorted - 1];
            a [numUnsorted - 1] = temp;
            numUnsorted--;
            for (long i = 0 ; i < 56000000 ; i++)
                ;

            printarray (a, size);

        }
    }

    //Bubble Sort
    public void bubble (int a[], int size)
    { //Pre: a is an array with values. It is of size size
        //Post: the values in a are put in ascending order

        int temp;

        for (int i = 0 ; i < size - 1 ; i++)
        {
            for (int j = 0 ; j < size - 1 - i ; j++)
            { // compare the two neighbours
                if (a [j + 1] < a [j])
                { //swap the neighbours if necessary
                    temp = a [j];
                    a [j] = a [j + 1];
                    a [j + 1] = temp;
                    for (long k = 0 ; k < 56000000 ; k++)
                        ;

                    printarray (a, size);

                }

            }
        }

    }

    //Insertion Sort
    public void insertion (int data[], int n)
    { //Pre: 0<=n<=data.length
        //Post: Values in data[0..n-1] are in ascending order

        int numSorted = 1;
        int index;
        while (numSorted < n)
        {
            //take the first unsorted value
            int temp = data [numSorted];
            //.. and insert it among the sorted:
            for (index = numSorted ; index > 0 ; index--)
            {
                if (temp < data [index - 1])
                {
                    data [index] = data [index - 1];
                }
                else
                {
                    break;
                }
            }
            //re-insert value
            data [index] = temp;
             for (long k = 0 ; k < 56000000 ; k++)
                        ;
            printarray (data, n);
            numSorted++;
        }
    }
    
    


    public void reset ()
    {
        for (int i = 1 ; i <= 1000000 ; i++)
        {
            int index1 = (int) ((Math.random () * (size)));
            int index2 = (int) ((Math.random () * (size)));
            while (index1 == index2)
            {
                index2 = (int) ((Math.random () * (size)));
            }
            int temp = a [index1];
            a [index1] = a [index2];
            a [index2] = temp;
        }
        printarray (a,size);
    }
}

[aspire1]

This is one version. You might want to look up Generics as of course, only works with int[]

private static void mergeSort( int[] data )
    {
       
       if( data.length > 1 )
       {
         int midPoint = data.length / 2;
         int[] left = new int[ midPoint ];   
         int[] right = new int[ data.length - midPoint ];
         
         for( int i = 0; i < midPoint; i++)
         {
           left[ i ] = data[ i ];
         }
         
         for( int i = midPoint, j= 0; i < data.length; i++, j++)
         {
           right[ j ] = data[ i ];
         }
         
         mergeSort( left );
         mergeSort( right );
         merge( left, right, data );
       }
     
    }
    
    private static void merge( int[] left, int[] right, int[] data )
    {
      int i = 0;
      int j = 0;
      int index = 0;
      
      while( i < left.length && j < right.length )
      {
        if( left[ i ] <= right[ j ] )
        {
            data[ index++ ] = left[ i++ ];
        }
        else
        {
          data[ index++ ] = right[ j++ ];
        }
       
      }
      
      while( i < left.length )
      {
         data[ index++ ] = left[ i ++ ]; 
      }
      
      while( j < right.length )
      {
        data[ index++ ] = right[ j++ ];
      }
    
    }

[insanely_sane]

This is one version. You might want to look up Generics as of course, only works with int[]

private static void mergeSort( int[] data )
    {
       
       if( data.length > 1 )
       {
         int midPoint = data.length / 2;
         int[] left = new int[ midPoint ];   
         int[] right = new int[ data.length - midPoint ];
         
         for( int i = 0; i < midPoint; i++)
         {
           left[ i ] = data[ i ];
         }
         
         for( int i = midPoint, j= 0; i < data.length; i++, j++)
         {
           right[ j ] = data[ i ];
         }
         
         mergeSort( left );
         mergeSort( right );
         merge( left, right, data );
       }
     
    }
    
    private static void merge( int[] left, int[] right, int[] data )
    {
      int i = 0;
      int j = 0;
      int index = 0;
      
      while( i < left.length && j < right.length )
      {
        if( left[ i ] <= right[ j ] )
        {
            data[ index++ ] = left[ i++ ];
        }
        else
        {
          data[ index++ ] = right[ j++ ];
        }
       
      }
      
      while( i < left.length )
      {
         data[ index++ ] = left[ i ++ ]; 
      }
      
      while( j < right.length )
      {
        data[ index++ ] = right[ j++ ];
      }
    
    }

Thank you so much :D