Generic Recursive Merge Sort in Java

Merge sort (also commonly spelled mergesort) is an O(n log n) comparison-based sorting algorithm. 

Conceptually, a 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.

Merge sort animation. The sorted elements are represented by dots.

package interviewquestions;

import java.util.Arrays;
import java.util.Comparator;

public class MergeSortRoutine {

   public static <K> void merge(K[] S1, K[] S2, K[] S, Comparator<K> comp) {

     int i = 0, j = 0;
     while (i + j < S.length) {
         if (j == S2.length || (i < S1.length && comp.compare(S1[i], S2[j]) < 0))
            S[i + j] = S1[i++]; 
         else
            S[i + j] = S2[j++]; 
     }

   }

   public static <K> void mergeSort(K[] S, Comparator<K> comp) {

     int n = S.length;
     if (n < 2)
        return; 

     int mid = n / 2;
     K[] S1 = Arrays.copyOfRange(S, 0, mid); 
     K[] S2 = Arrays.copyOfRange(S, mid, n);

     mergeSort(S1, comp); 
     mergeSort(S2, comp);

     merge(S1, S2, S, comp);
   }

   private static class IntComparator<T extends Comparable<T>> implements Comparator<T> {
     public int compare(T a, T b) {
      return a.compareTo(b);
     } 
   }

   public static void main(String[] args) {

     Integer[] inputArr = { 45, 23, 11, 89, 77, 98, 4, 28, 65, 43 };  
  
     System.out.println("Before sorting integer array with generic mergesort ");
     for (int i = 0; i < inputArr.length; i++) {
       System.out.print(inputArr[i]+" ");
     }
    
     mergeSort( inputArr, new IntComparator<Integer>() );
  
     System.out.println("\nAfter sorting integer array with generic mergesort ");
     for (int i = 0; i < inputArr.length; i++) {
       System.out.print(inputArr[i]+" ");
     }
  
     String[] values = { "asd","basd","cwe", "awe", "vasd" };
  
     System.out.println("\n\nBefore sorting String array with generic mergesort ");
     for (int i = 0; i < values.length; i++) {
       System.out.print(values[i]+" ");
     }
  
     mergeSort(values, new IntComparator<String>());
  
     System.out.println("\nAfter sorting String array with generic mergesort ");
     for (int i = 0; i < values.length; i++) {
       System.out.print(values[i]+" ");
     }
   }
}

Above Mergesort works for types that implements Comparable interface. Generic Comparator class instace is passed as a parameter to the generic mergeSort method.

Create a MergeSortRoutine.java file in your workspace.

When the main method inside the MergeSortRoutine class executed it is going to print :

Before sorting integer array with generic mergesort
45 23 11 89 77 98 4 28 65 43
After sorting integer array with generic mergesort
4 11 23 28 43 45 65 77 89 98

Before sorting String array with generic mergesort
asd basd cwe awe vasd
After sorting String array with generic mergesort
asd awe basd cwe vasd