1 public class Merge { 2      3     private static Comparable[] aux; 4     private static void exch(Comparable[] a, int i, int j) { 5         Comparable tmp = a[i]; 6         a[i] = a[j]; 7         a[j] = tmp; 8     } 9 10     private static boolean less(Comparable a, Comparable b) {11         return (a.compareTo(b) < 0);12     }13 14     private static void show(Comparable[] a) {15         int N = a.length;16         for (int i = 0; i < N; i++) {17             System.out.print(a[i] + " ");18         }19         System.out.println();20     }21 22     public static boolean isSorted(Comparable[] a) {23         int N = a.length;24         for (int i = 1; i < N; i++) {25             if (less(a[i], a[i - 1]))26                 return false;27         }28         return true;29     }30 31     private static void merge(Comparable[] a, int lo, int mid, int hi)32     {33         for(int k = lo; k <= hi; k++)34         {35             aux[k] = a[k];36         }37         int i = lo;38         int j = mid + 1;39         for(int k = lo; k <= hi; k++)40         {41             if( i > mid) a[k] = aux[j++];42             else if(j > hi) a[k] = aux[i++];43             else if(less(aux[j], aux[i])) a[k] = aux[j++];44             else a[k] = aux[i++];45         }46     }47     48     private static void sort(Comparable[] a, int lo, int hi)49     {50         if(hi <= lo) return;51         int mid = lo + (hi - lo) / 2;52         sort(a, lo, mid);53         sort(a, mid + 1, hi);54         merge(a, lo, mid, hi);55     }56 57     public static void sort(Comparable[] a)58     {59         aux =new Comparable[a.length];60         sort(a, 0, a.length - 1);61     }62     public static void main(String[] args) {63         String[] a = In.readStrings();64         sort(a);65         show(a);66     }67 68 }

 1 import java.awt.datatransfer.StringSelection; 2  3  4 public class MergeBP { 5  6     private static Comparable[] aux; 7     private static void exch(Comparable[] a, int i, int j) { 8         Comparable tmp = a[i]; 9         a[i] = a[j];10         a[j] = tmp;11     }12 13     private static boolean less(Comparable a, Comparable b) {14         return (a.compareTo(b) < 0);15     }16 17     private static void show(Comparable[] a) {18         int N = a.length;19         for (int i = 0; i < N; i++) {20             System.out.print(a[i] + " ");21         }22         System.out.println();23     }24 25     public static boolean isSorted(Comparable[] a) {26         int N = a.length;27         for (int i = 1; i < N; i++) {28             if (less(a[i], a[i - 1]))29                 return false;30         }31         return true;32     }33 34     private static void merge(Comparable[] a, int lo, int mid, int hi)35     {36         for(int k = lo; k <= hi; k++)37         {38             aux[k] = a[k];39         }40         int i = lo;41         int j = mid + 1;42         for(int k = lo; k <= hi; k++)43         {44             if( i > mid) a[k] = aux[j++];45             else if(j > hi) a[k] = aux[i++];46             else if(less(aux[j], aux[i])) a[k] = aux[j++];47             else a[k] = aux[i++];48         }49     }50     51     public static void sort(Comparable[] a)52     {53         int N = a.length;54         aux = new Comparable[N];55         for(int sz = 1; sz < N; sz += sz)56         {57             for(int lo = 0; lo < N - sz; lo += sz + sz)58             {59                 merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));60             }61         }62     }63     public static void main(String[] args) {64         String[] a = In.readStrings();65         sort(a);66         show(a);67     }68 69 }