Merge Sort Algorithm using Generics in Java

Today, we are going to show the implementation of the Merge Sort algorithm, which is the fifth one from our series of tutorials on sorting algorithms. If you haven’t read the first four tutorials on BubbleSort, InsertionSort, SelectionSort and CountingSort, I strongly recommend that you go there and read them, because we will reuse code that was explained there.

The application is really simple, it will just get an instance of a Sortable algorithm, which in this case will be a MergeSort object and pass some Integer and String arrays to it, but any object that implements Comparable can be passed as a parameter as well, then it will print the elements from the sorted arrays.

public class SorterApp {
  public static void main(String[] args) {
    SorterApp app = new SorterApp();
    app.run();
  }

  private void run() {
    sort(new Integer[] { 2, 42, -3, 2, 4 });
    sort(new Integer[] { 1, 2, 3, 4, 5 });
    sort(new Integer[] { 3, 1, 5, 4, 2 });
    sort(new Integer[] { 5, 4, 3, 2, 1 });

    System.out.println();

    sort(new String[] { "a", "b", "c", "d", "e" });
    sort(new String[] { "c", "a", "e", "d", "b" });
    sort(new String[] { "e", "d", "c", "b", "a" });
  }

  private &amp;lt;T&amp;gt; extends Comparable&amp;lt;T&amp;gt; void sort(T[] values) {
    Sortable sorter = newSortable(5);
    sorter.sortAscending(values);
    // sorter.sortDescending(values);
    Utils.printArray(values);
  }

  private Sortable newSortable(int sortableAlgorithm) {
    switch (sortableAlgorithm) {
      case 1:
        return new BubbleSort();
      case 2:
        return new InsertionSort();
      case 3:
        return new SelectionSort();
      case 4:
        return new CountingSort();
      case 5:
        return new MergeSort();
      default:
        return new BubbleSort();
    }
  }
}

You can see in the code below that the sortAscending and sortDescending invoke the same private method mergeSort with the difference of just one parameter. This is done because the code to sort in ascending or descending order is pretty much the same; the difference is just one small detail.

The Sorter Abstract class and the Sortable Interface were explained in the first tutorial of our series.

public class SelectionSort extends Sorter implements Sortable {
  private int count = 0;

  @Override
  public &amp;lt;T&amp;gt; extends Comparable&amp;lt;T&amp;gt; void sortAscending(T[] values) {
    count = 0;
    mergeSort(values, 0, values.length - 1, 0);

    System.out.printf("%2s: ", count);
  }

  @Override
  public &amp;lt;T&amp;gt; extends Comparable&amp;lt;T&amp;gt; void sortDescending(T[] values) {
    count = 0;
    mergeSort(values, 0, values.length - 1, 1);

    System.out.printf("%2s: ", count);
  }

The Merge Sort implementation will create some temporary arrays and to do that, we added a method into the Utils class:

  public static &amp;lt;T&amp;gt; List&amp;lt;T&amp;gt; newList(int initialCapacity) {
    return new ArrayList&amp;lt;T&amp;gt;(initialCapacity);
  }

Just like Bubble Sort, Insertion Sort and Selection Sort, the Merge Sort is a comparison sort type of algorithm, which means, it sorts its elements by doing comparisons between two elements at a time, but unlike the others, the most common implementations of Merge Sort do not sort in-place and because of this, they require more memory.

  private &amp;lt;T&amp;gt; extends Comparable&amp;lt;T&amp;gt; void mergeSort(T[] arValues, int low, int high, int orderType) {
    if (low &amp;lt; high) {
      // Get the middle of the array.
      int middle = low + ((high - low) / 2);

      // Divide.
      mergeSort(arValues, low, middle, orderType);
      mergeSort(arValues, middle + 1, high, orderType);

      // Conquer.
      merge(arValues, low, middle, high, orderType);
    }
  }

  private &amp;lt;T&amp;gt; extends comparable&amp;lt;T&amp;gt; void merge(T[] arValues, int low, int middle, int high, int orderType) {
    // The amount of numbers to sort.
    int numbersToSort = (high - low) + 1;

    // Temp array to contain the sorted elements of this iteration.
    List&amp;lt;T&amp;gt; arTemp = Utils.newList(numbersToSort);

    int i = low;
    int j = middle + 1;
    T lowValue = null;
    T highValue = null;
    for (int k = 0; k &amp;lt; numbersToSort; k++) {
      count++;

      lowValue = (i &amp;lt;= middle) ? arValues[i] : null;
      highValue = (j &amp;lt;= high) ? arValues[j] : null;

      if (checkBiggerSmaller(lowValue, highValue, orderType)) {
        arTemp.add(arValues[i++]);
      } else {
        arTemp.add(arValues[j++]);
      }
    }

    // Transfer the sorted elements to the original array.
    for (int k = 0; k &amp;lt; numbersToSort; k++) {
      count++;
      arValues[low + k] = arTemp.get(k);
    }
  }

  private &amp;lt;T&amp;gt; extends comparable&amp;lt;T&amp;gt; boolean checkBiggerSmaller(T lowValue, T highValue, int orderType) {
    if ((lowValue != null) &amp;&amp; (highValue == null)) {
      return true;
    } else if ((lowValue == null) &amp;&amp; (highValue != null)) {
      return false;
    }

    if (0 == orderType) {
      // Ascending.
      return lowValue.compareTo(highValue) &lt;= 0;
    } else {
      // Descending.
      return lowValue.compareTo(highValue) &lt;= 0;
    }
  }
}