Merge Sort Java

Merge sort works as follows:

1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).

2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

Merger Sort Works in O(nlogn) time in best, average, worst cases.

Following video explains merge sort clearly.

https://www.youtube.com/watch?v=TzeBrDU-JaY

import java.util.Objects;

public class MergeSort<T extends Comparable<T>> {
 private T arr[];
 private boolean isAscending;

 /**
  * If flag is true, then elements are sorted in ascending order, else
  * descending order
  */
 public void sort(T arr[], boolean flag) {
  Objects.nonNull(arr);
  this.arr = arr;
  isAscending = flag;
  if (flag == true)
   sortAscending(0, arr.length - 1);
  else
   sortDescending(0, arr.length - 1);
 }

 private void sortAscending(int left, int right) {
  int mid = (left + right) / 2;
  if (left < right) {
   sortAscending(left, mid);
   sortAscending(mid + 1, right);
   merge(left, mid, right);
  }

 }

 private void sortDescending(int left, int right) {
  int mid = (left + right) / 2;
  if (left < right) {
   sortDescending(left, mid);
   sortDescending(mid + 1, right);
   merge(left, mid, right);
  }

 }

 /* If falg is true compare for ascending order, else descending order */
 private boolean compare(T elem1, T elem2) {
  return elem1.compareTo(elem2) <= 0;
 }

 @SuppressWarnings("unchecked")
 private void merge(int left, int mid, int right) {
  int low = left, high = mid + 1, k;
  Object temp[] = new Object[right - left + 1];
  int counter = 0;

  if (isAscending)
   while (low <= mid && high <= right) {
    if (compare(arr[low], arr[high]))
     temp[counter++] = arr[low++];
    else
     temp[counter++] = arr[high++];

   }
  else {
   while (low <= mid && high <= right) {
    if (compare(arr[high], arr[low]))
     temp[counter++] = arr[low++];
    else
     temp[counter++] = arr[high++];
   }
  }

  if (low > mid)
   for (k = high; k <= right; k++)
    temp[counter++] = arr[k];
  else
   for (k = low; k <= mid; k++)
    temp[counter++] = arr[k];

  counter = 0;
  for (k = left; k <= right; k++)
   arr[k] = (T) temp[counter++];
 }

}

Following is the junit test case for above program.

import static org.junit.Assert.assertTrue;

import java.util.Arrays;

import org.junit.Test;

public class MergeSortTest {

 @Test
 public void test1() {
  MergeSort<Integer> obj1 = new MergeSort<>();

  Integer arr1[] = { 5, 46, 25, 13, 12 };
  Integer arr2[] = { 5, 46 };
  Integer arr3[] = { 5, 4, 3, 2, 1 };
  Integer arr4[] = { 1 };
  Integer arr5[] = { 1, 3, 5, 7, 2, 4, 6, 8 };

  obj1.sort(arr1, false);
  obj1.sort(arr2, false);
  obj1.sort(arr3, false);
  obj1.sort(arr4, false);
  obj1.sort(arr5, false);

  assertTrue(Arrays.equals(arr1, new Integer[] { 46, 25, 13, 12, 5 }));
  assertTrue(Arrays.equals(arr2, new Integer[] { 46, 5 }));
  assertTrue(Arrays.equals(arr3, new Integer[] { 5, 4, 3, 2, 1 }));
  assertTrue(Arrays.equals(arr4, new Integer[] { 1 }));
  assertTrue(Arrays
    .equals(arr5, new Integer[] { 8, 7, 6, 5, 4, 3, 2, 1 }));
 }

 @Test
 public void test2() {
  MergeSort<Integer> obj1 = new MergeSort<>();

  Integer arr1[] = { 5, 46, 25, 13, 12 };
  Integer arr2[] = { 5, 46 };
  Integer arr3[] = { 5, 4, 3, 2, 1 };
  Integer arr4[] = { 1 };
  Integer arr5[] = { 1, 3, 5, 7, 2, 4, 6, 8 };

  obj1.sort(arr1, true);
  obj1.sort(arr2, true);
  obj1.sort(arr3, true);
  obj1.sort(arr4, true);
  obj1.sort(arr5, true);

  assertTrue(Arrays.equals(arr1, new Integer[] { 5, 12, 13, 25, 46 }));
  assertTrue(Arrays.equals(arr2, new Integer[] { 5, 46 }));
  assertTrue(Arrays.equals(arr3, new Integer[] { 1, 2, 3, 4, 5 }));
  assertTrue(Arrays.equals(arr4, new Integer[] { 1 }));
  assertTrue(Arrays
    .equals(arr5, new Integer[] { 1, 2, 3, 4, 5, 6, 7, 8 }));
 }
}