Mergesort

Java Code

public class MERGESORT {

    static final int[] list = {32, 64, 3, 1, 0, 8, 16, 65536, 32768, 4, 2, 128, 256, 1024, 512, 2048, 4096, 16384, 8192};

    public static void main(String[] args) {
        MERGESORT main = new MERGESORT();
        int[] list_sorted = main.mergesort(list);
        System.out.println("unsorted array:");
        main.read(list);
        System.out.println("sorted array:");
        main.read(list_sorted);
    }

    /**
     * Prints out the argument array.
     *
     * @param array the argument array
     */
    void read(int[] array) {
        for (short i = 0; i < array.length; i++) {
            if (i == (array.length - 1)) {
                System.out.println(array[i]);
            } else {
                System.out.print(array[i] + " | ");
            }
        }
    }

    /**
     * Sorts the argument array.
     * Divides the argument array recursively until the subarrays contain one element.
     *
     * @param list the argument array
     * @return the sorted argument array
     */
    int[] mergesort(int[] list) {
        if (list.length <= 1) {
            return list;
        } else {
            int[] listleft = new int[list.length / 2];
            int[] listright = new int[(list.length - list.length / 2)];
            for (short i = 0; i < list.length; i++) {
                if (i < list.length / 2) {
                    listleft[i] = list[i];
                }
                if (i >= list.length / 2) {
                    listright[i - listleft.length] = list[i];
                }
            }
            /* recursively sort the list from left to right */
            listleft = mergesort(listleft);
            listright = mergesort(listright);
            return merge(listleft, listright);
        }
    }

    /**
     * Merges the sorted argument arrays.
     *
     * @param listleft  the sorted argument array
     * @param listright the sorted argument array
     * @return the merged array
     */
    int[] merge(int[] listleft, int[] listright) {
        int[] list = new int[listleft.length + listright.length];
        int i = 0, left = 0, right = 0;
        while (left < listleft.length && right < listright.length) {
            if (listleft[left] < listright[right])
                list[i++] = listleft[left++];
            else
                list[i++] = listright[right++];
        }
        while (left < listleft.length)
            list[i++] = listleft[left++];
        while (right < listright.length)
            list[i++] = listright[right++];
        return list;
    }
}

unsorted array:
32 | 64 | 3 | 1 | 0 | 8 | 16 | 65536 | 32768 | 4 | 2 | 128 | 256 | 1024 | 512 | 2048 | 4096 | 16384 | 8192
sorted array:
0 | 1 | 2 | 3 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 | 4096 | 8192 | 16384 | 32768 | 65536

$ javac MERGESORT.java
$ java MERGESORT