sort/MergeSort.java

Go to the documentation of this file.

package sort;

import java.util.ArrayList;

public class MergeSort<T extends Comparable<T>> {

    protected void merge(ArrayList<T> vals, ArrayList<T> temp, int left, int mid, int right) {
        // we have two halves, bounded by left, left_end, mid and right
        int left_end = mid - 1;
        int n = (right - left) + 1;
        int ix = left;
        // Do an ordered copy into the temp array
        while (left <= left_end && mid <= right) {
            if (vals.get(left).compareTo(vals.get(mid)) <= 0) {
                temp.set(ix, vals.get(left));
                ix++;
                left++;
            } else {
                temp.set(ix, vals.get(mid));
                ix++;
                mid++;
            }
        } // while
          // copy any remaining values that were not copied above
        while (left <= left_end) {
            temp.set(ix, vals.get(left));
            ix++;
            left++;
        }
        while (mid <= right) {
            temp.set(ix, vals.get(mid));
            ix++;
            mid++;
        }
        // copy the sorted values back into the val array from the temp array.
        // The only
        // reason the copy is being down from right down to (right - n) is that
        // right
        // the the only variable left that has the original index information
        // left.
        for (int i = 0; i < n; i++) {
            vals.set(right, temp.get(right));
            right--;
        }
    } // merge

    protected void m_sort(ArrayList<T> vals, ArrayList<T> temp, int left, int right) {
        if (right > left) {
            int mid = (right + left) / 2; // mid-point
            m_sort(vals, temp, left, mid);
            m_sort(vals, temp, mid + 1, right);
            merge(vals, temp, left, mid + 1, right);
        }
    } // m_sort

    public void mergeSort(ArrayList<T> vals) {
        if (vals != null && vals.size() > 1) {
            int len = vals.size();
            ArrayList<T> temp = new ArrayList<T>(len);
            for (int i = 0; i < len; i++) {
                temp.add(null);
            }
            m_sort(vals, temp, 0, len - 1);
        }
    }

}