Viewing file: java/MergeSort.java | Back to directory listing
Author: Loren Segal | Last modified: February 20 2006 07:00 pm | Download

/**
 * The MergeSort algorithm, as discussed in COMP239
 * 
 * The main function sorts the set: {1,6,3,4,7,3,2}
 * 
 * @author Loren Segal
 * @version 1.0
 */
public class MergeSort
{
    public int[] merge(int[] set)
    {
        if (set.length > 1) 
        {
            int n = set.length / 2;
            int[] low = new int[n];
            int[] high = new int[set.length-n];
            for (int i = 0; i < set.length; i++)
            {
                if (i < n) { low[i] = set[i]; }
                else { high[i-n] = set[i]; }
            }
            return merge(merge(low), merge(high));
        }
        return set;
    }
    
    public int[] merge(int[] a, int[] b)
    {
        int d = 0, i = 0, j = 0;
        int[] c = new int[a.length + b.length];
        while (i < a.length && j < b.length)
        {
            c[d++] = (a[i] < b[j] ? a[i++] : b[j++]);
            if (i == a.length) { for(;j<b.length;j++) c[d++] = b[j]; }
            else if (j == b.length) { for(;i<a.length;i++) c[d++] = a[i]; }
        }
        return c;
    }
 
    public MergeSort(int[] set)
    {
        int[] sortedSet = merge(set);
        printArray(sortedSet);
    }
    
    public void printArray(int[] a) 
    { 
        for(int i = 0; i < a.length - 1; i++)
        {
            System.out.print(a[i] + ", ");
        }
        System.out.println(a[a.length-1]);
    }
    
    public static void main(String[] args)
    {
        int set[] = {1,6,3,4,7,3,2};
        new MergeSort(set);
    }
}