// This program implements the merge sort algorithm for
// arrays of objects implementing the Comparable interface.

import java.util.*;

public class MergeSort {
    public static void main(String[] args) {
        Integer[] list = {14, 32, 67, 76, 23, 41, 58, 85};
        System.out.println("before: " + Arrays.toString(list));
        mergeSort(list);
        System.out.println("after:  " + Arrays.toString(list));
    }

    // Places the elements of the given array into sorted order
    // using the merge sort algorithm.
    // postcondition: array is in sorted (nondecreasing) order
    public static void mergeSort(Comparable[] a) {
        if (a.length > 1) {
            // split array into two halves
            Comparable[] left = Arrays.copyOfRange(a, 0, a.length / 2);
            Comparable[] right = Arrays.copyOfRange(a, a.length / 2, a.length);
            
            // recursively sort the two halves
            mergeSort(left);
            mergeSort(right);
            
            // merge the sorted halves into a sorted whole
            merge(a, left, right);
        }
    }
    
    // Merges the given left and right arrays into the given 
    // result array.  
    // precondition : result is empty; left/right are sorted
    // postcondition: result contains result of merging sorted lists;
    public static void merge(Comparable[] result, 
                             Comparable[] left, Comparable[] right) {
        int i1 = 0;   // index into left array
        int i2 = 0;   // index into right array
        
        for (int i = 0; i < result.length; i++) {
            if (i2 >= right.length || (i1 < left.length && 
                    left[i1].compareTo(right[i2]) <= 0)) {
                result[i] = left[i1];    // take from left
                i1++;
            } else {
                result[i] = right[i2];   // take from right
                i2++;
            }
        }
    }
 }