//Bottom-up mergesort: Java implementation

public class MergeBU

{

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi)

{

assert isSorted(a, lo, mid);

// precondition: a[lo..mid] sorted

assert isSorted(a, mid+1, hi); // precondition: a[mid+1..hi] sorted

for (int k = lo; k <= hi; k++)

aux[k] = a[k];

int i = lo, j = mid+1;

for (int k = lo; k <= hi; k++)

{

if (i > mid) a[k]=aux[j++];

else if (j > hi) a[k]=aux[i++];

else if (less(aux[j], aux[i])) a[k]=aux[j++];

else a[k]=aux[i++];

}

assert isSorted(a, lo, hi);

}

private static boolean isSorted(Comparable[] a, int lo, int hi) {

for (int i = lo + 1; i <= hi; i++)

if (less(a[i], a[i-1])) return false;

return true;

}

private static boolean less(Comparable v, Comparable w)

{

return (v.compareTo(w) < 0);

}

//private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)

//{

//if (hi <= lo) return;// improve this by using insertion sort

//int mid = lo + (hi - lo) / 2;

//sort(a, aux, lo, mid);

//sort(a, aux, mid+1, hi);

////another improvement

//// if (!less(a[mid+1], a[mid])) return;

//merge(a, aux, lo, mid, hi);

//}

public static void sort(Comparable[] a)

{

int N = a.length;

Comparable[] aux = new Comparable[N];

for (int sz = 1; sz < N; sz = sz+sz)

for (int lo = 0; lo < N-sz; lo += sz+sz)

merge(a, aux, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));

}

//Client

public static void main(String[] args){

// int[] a={4,2,5,2,65,1,6,3,7,2};

String[] a={"cat","abh","viki","shy","rom"};

for(int p=0;p<5;p++)

System.out.print(a[p]+",");

System.out.println("");

sort(a);

for(int p=0;p<5;p++)

System.out.print(a[p]+",");

}

}