// Path: Java-data-Structures/src/main/java/com/sorting/MergeSort.java
// public class MergeSort {
// 
//     /**
//      * Use the merge sort method to sort the given array A
//      * 
//      * @param A
//      *            Array of Comparable that contains the object to sort
//      */
//     public static void sort(Comparable[] A) {
//         if (A == null)
//             return;
//         sort(A, 0, A.length - 1);
//     }
// 
//     private static void sort(Comparable[] A, int lo, int hi) {
//         if (lo >= hi)
//             return;
//         int mid = lo + (hi - lo) / 2;
//         sort(A, lo, mid);
//         sort(A, mid + 1, hi);
//         merge(A, lo, mid, hi);
//     }
// 
//     private static void merge(Comparable[] A, int lo, int mid, int hi) {
//         int leftSize = mid - lo + 1;
//         int rightSize = hi - mid;
//         Comparable[] left = new Comparable[leftSize];
//         Comparable[] right = new Comparable[rightSize];
// 
//         for (int i = 0; i < leftSize; i++)
//             left[i] = A[lo + i];
// 
//         for (int i = 0; i < rightSize; i++)
//             right[i] = A[mid + i + 1];
// 
//         int leftPt = 0;
//         int rightPt = 0;
//         for (int i = lo; i <= hi; i++) {
//             if (leftPt >= leftSize) {
//                 A[i] = right[rightPt];
//                 rightPt++;
//             } else if (rightPt >= rightSize) {
//                 A[i] = left[leftPt];
//                 leftPt++;
//             } else {
//                 if (less(right[rightPt], left[leftPt])) {
//                     A[i] = right[rightPt];
//                     rightPt++;
//                 } else {
//                     A[i] = left[leftPt];
//                     leftPt++;
//                 }
//             }
//         }
//     }
// 
//     private static boolean less(Comparable a, Comparable b) {
//         int cmp = a.compareTo(b);
//         if (cmp < 0)
//             return true;
//         return false;
//     }
// 
// }


import com.sorting.MergeSort;
import junit.framework.TestCase;
package com.test.sorting;



public class TestMergeSort extends TestCase {

    public void testMergeSort() {

        String[] A = { "zs", "qw", "qr", "miguel", "rtd", "fgs", "qq", "mk", "slao", "oiu", "vf", "xs", "er", "qw",
                "bv" };
        Integer[] B = { 2, 4, 7, 542, 0, 1, 3, 0, 6, 2, 7, 9, 10, 2, 4, 6, 0, 3, 2, 9, 2, 77, 33, 22, 5, 4, 2, 2, 2 };

// Path: Java-data-Structures/src/main/java/com/sorting/MergeSort.java
// public class MergeSort {
// 
//     /**
//      * Use the merge sort method to sort the given array A
//      * 
//      * @param A
//      *            Array of Comparable that contains the object to sort
//      */
//     public static void sort(Comparable[] A) {
//         if (A == null)
//             return;
//         sort(A, 0, A.length - 1);
//     }
// 
//     private static void sort(Comparable[] A, int lo, int hi) {
//         if (lo >= hi)
//             return;
//         int mid = lo + (hi - lo) / 2;
//         sort(A, lo, mid);
//         sort(A, mid + 1, hi);
//         merge(A, lo, mid, hi);
//     }
// 
//     private static void merge(Comparable[] A, int lo, int mid, int hi) {
//         int leftSize = mid - lo + 1;
//         int rightSize = hi - mid;
//         Comparable[] left = new Comparable[leftSize];
//         Comparable[] right = new Comparable[rightSize];
// 
//         for (int i = 0; i < leftSize; i++)
//             left[i] = A[lo + i];
// 
//         for (int i = 0; i < rightSize; i++)
//             right[i] = A[mid + i + 1];
// 
//         int leftPt = 0;
//         int rightPt = 0;
//         for (int i = lo; i <= hi; i++) {
//             if (leftPt >= leftSize) {
//                 A[i] = right[rightPt];
//                 rightPt++;
//             } else if (rightPt >= rightSize) {
//                 A[i] = left[leftPt];
//                 leftPt++;
//             } else {
//                 if (less(right[rightPt], left[leftPt])) {
//                     A[i] = right[rightPt];
//                     rightPt++;
//                 } else {
//                     A[i] = left[leftPt];
//                     leftPt++;
//                 }
//             }
//         }
//     }
// 
//     private static boolean less(Comparable a, Comparable b) {
//         int cmp = a.compareTo(b);
//         if (cmp < 0)
//             return true;
//         return false;
//     }
// 
// }


// Path: Java-data-Structures/src/test/java/com/test/sorting/TestMergeSort.java
import com.sorting.MergeSort;
import junit.framework.TestCase;

package com.test.sorting;



public class TestMergeSort extends TestCase {

    public void testMergeSort() {

        String[] A = { "zs", "qw", "qr", "miguel", "rtd", "fgs", "qq", "mk", "slao", "oiu", "vf", "xs", "er", "qw",
                "bv" };
        Integer[] B = { 2, 4, 7, 542, 0, 1, 3, 0, 6, 2, 7, 9, 10, 2, 4, 6, 0, 3, 2, 9, 2, 77, 33, 22, 5, 4, 2, 2, 2 };

        MergeSort.sort(A);