JavaAlgorithms Elementary and no so elementary Java algorithms
sort/MergeSort.java
Go to the documentation of this file.
```00001
00014 package sort;
00015
00016 import java.util.ArrayList;
00017
00048 public class MergeSort<T extends Comparable<T>> {
00049
00065     protected void merge(ArrayList<T> vals, ArrayList<T> temp, int left, int mid, int right) {
00066         // we have two halves, bounded by left, left_end, mid and right
00067         int left_end = mid - 1;
00068         int n = (right - left) + 1;
00069         int ix = left;
00070         // Do an ordered copy into the temp array
00071         while (left <= left_end && mid <= right) {
00072             if (vals.get(left).compareTo(vals.get(mid)) <= 0) {
00073                 temp.set(ix, vals.get(left));
00074                 ix++;
00075                 left++;
00076             } else {
00077                 temp.set(ix, vals.get(mid));
00078                 ix++;
00079                 mid++;
00080             }
00081         } // while
00082           // copy any remaining values that were not copied above
00083         while (left <= left_end) {
00084             temp.set(ix, vals.get(left));
00085             ix++;
00086             left++;
00087         }
00088         while (mid <= right) {
00089             temp.set(ix, vals.get(mid));
00090             ix++;
00091             mid++;
00092         }
00093         // copy the sorted values back into the val array from the temp array.
00094         // The only
00095         // reason the copy is being down from right down to (right - n) is that
00096         // right
00097         // the the only variable left that has the original index information
00098         // left.
00099         for (int i = 0; i < n; i++) {
00100             vals.set(right, temp.get(right));
00101             right--;
00102         }
00103     } // merge
00104
00116     protected void m_sort(ArrayList<T> vals, ArrayList<T> temp, int left, int right) {
00117         if (right > left) {
00118             int mid = (right + left) / 2; // mid-point
00119             m_sort(vals, temp, left, mid);
00120             m_sort(vals, temp, mid + 1, right);
00121             merge(vals, temp, left, mid + 1, right);
00122         }
00123     } // m_sort
00124
00140     public void mergeSort(ArrayList<T> vals) {
00141         if (vals != null && vals.size() > 1) {
00142             int len = vals.size();
00143             ArrayList<T> temp = new ArrayList<T>(len);
00144             for (int i = 0; i < len; i++) {