Generic NonRecursive BottomUp Merge Sort in Java

MergeSort can also be implemented with a non-recursive bottom-up approach.

Non-recursive bottom-up merge-sort runs in O(nlogn) time as recursive version does.

It is considered a bit faster than recursive merge-sort in practice because it does not make recursive-calls.

There is a detailed description about this implementation at here.

package interviewquestions;

import java.util.Comparator;

public class MergeSortRoutine {

 public static <K> void merge(K[] in, K[] out, Comparator<K> comp, int start, int inc) {

  int end1 = Math.min(start + inc, in.length);
  int end2 = Math.min(start + 2 * inc, in.length);
  int x = start;
  int y = start + inc;
  int z = start;
  
  while (x < end1 && y < end2)
   if (comp.compare(in[x], in[y]) < 0)
    out[z++] = in[x++];
   else
    out[z++] = in[y++];
  
  if (x < end1)
   System.arraycopy(in, x, out, z, end1 - x);
  else if (y < end2)
   System.arraycopy(in, y, out, z, end2 - y);
 }

 public static <K> void mergeSortBottomUp(K[] orig, Comparator<K> comp) {
  
  int n = orig.length;
  K[] src = orig;
  K[] dest = (K[]) new Object[n];
  K[] temp;
  for (int i = 1; i < n; i *= 2) { 
   
   for (int j = 0; j < n; j += 2 * i)
    merge(src, dest, comp, j, i);
   
   temp = src;
   src = dest;
   dest = temp;
  }
  if (orig != src)
   System.arraycopy(src, 0, orig, 0, n);
 }

 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] + " ");
  }

  mergeSortBottomUp(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] + " ");
  }

  mergeSortBottomUp(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 Non-recursive bottom-up Mergesort works for types that implements Comparable interface. Generic Comparator class instace is passed as a parameter to the generic mergeSortBottomUp 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