001// Exercise 2.2.9 2.2.20 (Solution published at http://algs4.cs.princeton.edu/)
002package algs22;
003import stdlib.*;
004/* ***********************************************************************
005 *  Compilation:  javac Merge.java
006 *  Execution:    java Merge < input.txt
007 *  Dependencies: StdOut.java StdIn.java
008 *  Data files:   http://algs4.cs.princeton.edu/22merge/tiny.txt
009 *                http://algs4.cs.princeton.edu/22merge/words3.txt
010 *
011 *  Sorts a sequence of strings from standard input using mergesort.
012 *
013 *  % more tiny.txt
014 *  S O R T E X A M P L E
015 *
016 *  % java Merge < tiny.txt
017 *  A E E L M O P R S T X                 [ one string per line ]
018 *
019 *  % more words3.txt
020 *  bed bug dad yes zoo ... all bad yet
021 *
022 *  % java Merge < words3.txt
023 *  all bad bed bug dad ... yes yet zoo    [ one string per line ]
024 *
025 *************************************************************************/
026
027public class Merge {
028
029        // stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi]
030        public static <T extends Comparable<? super T>> void merge(T[] a, T[] aux, int lo, int mid, int hi) {
031
032                // precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
033                assert isSorted(a, lo, mid);
034                assert isSorted(a, mid+1, hi);
035
036                // copy to aux[]
037                for (int k = lo; k <= hi; k++) {
038                        aux[k] = a[k];
039                }
040
041                // merge back to a[]
042                int i = lo, j = mid+1;
043                for (int k = lo; k <= hi; k++) {
044                        if      (i > mid)              a[k] = aux[j++];
045                        else if (j > hi)               a[k] = aux[i++];
046                        else if (less(aux[j], aux[i])) a[k] = aux[j++];
047                        else                           a[k] = aux[i++];
048                }
049                if (COUNT_OPS) DoublingTest.addOps (hi-lo);
050
051                // postcondition: a[lo .. hi] is sorted
052                assert isSorted(a, lo, hi);
053        }
054
055        // mergesort a[lo..hi] using auxiliary array aux[lo..hi]
056        private static <T extends Comparable<? super T>> void sort(T[] a, T[] aux, int lo, int hi) {
057                if (hi <= lo) return;
058                int mid = lo + (hi - lo) / 2;
059                sort(a, aux, lo, mid);
060                sort(a, aux, mid + 1, hi);
061                merge(a, aux, lo, mid, hi);
062        }
063
064        @SuppressWarnings("unchecked")
065        public static <T extends Comparable<? super T>> void sort(T[] a) {
066                T[] aux = (T[]) new Comparable[a.length];
067                sort(a, aux, 0, a.length-1);
068                assert isSorted(a);
069        }
070
071
072        /* *********************************************************************
073         *  Helper sorting functions
074         ***********************************************************************/
075
076        // is v < w ?
077        private static <T extends Comparable<? super T>> boolean less(T v, T w) {
078                if (COUNT_OPS) DoublingTest.incOps ();
079                return (v.compareTo(w) < 0);
080        }
081
082        /* *********************************************************************
083         *  Check if array is sorted - useful for debugging
084         ***********************************************************************/
085        private static <T extends Comparable<? super T>> boolean isSorted(T[] a) {
086                return isSorted(a, 0, a.length - 1);
087        }
088
089        private static <T extends Comparable<? super T>> boolean isSorted(T[] a, int lo, int hi) {
090                for (int i = lo + 1; i <= hi; i++)
091                        if (less(a[i], a[i-1])) return false;
092                return true;
093        }
094
095
096        /* *********************************************************************
097         *  Index mergesort
098         ***********************************************************************/
099        // stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi]
100        private static <T extends Comparable<? super T>> void merge(T[] a, int[] index, int[] aux, int lo, int mid, int hi) {
101
102                // copy to aux[]
103                for (int k = lo; k <= hi; k++) {
104                        aux[k] = index[k];
105                }
106
107                // merge back to a[]
108                int i = lo, j = mid+1;
109                for (int k = lo; k <= hi; k++) {
110                        if      (i > mid)                    index[k] = aux[j++];
111                        else if (j > hi)                     index[k] = aux[i++];
112                        else if (less(a[aux[j]], a[aux[i]])) index[k] = aux[j++];
113                        else                                 index[k] = aux[i++];
114                }
115        }
116
117        // return a permutation that gives the elements in a[] in ascending order
118        // do not change the original array a[]
119        public static <T extends Comparable<? super T>> int[] indexSort(T[] a) {
120                int N = a.length;
121                int[] index = new int[N];
122                for (int i = 0; i < N; i++)
123                        index[i] = i;
124
125                int[] aux = new int[N];
126                indexSort(a, index, aux, 0, N-1);
127                return index;
128        }
129
130        // mergesort a[lo..hi] using auxiliary array aux[lo..hi]
131        private static <T extends Comparable<? super T>> void indexSort(T[] a, int[] index, int[] aux, int lo, int hi) {
132                if (hi <= lo) return;
133                int mid = lo + (hi - lo) / 2;
134                indexSort(a, index, aux, lo, mid);
135                indexSort(a, index, aux, mid + 1, hi);
136                merge(a, index, aux, lo, mid, hi);
137        }
138
139        // print array to standard output
140        private static <T> void show(T[] a) {
141                for (T element : a) {
142                        StdOut.println(element);
143                }
144        }
145
146        // test code
147        private static boolean COUNT_OPS = false;
148        public static void main(String[] args) {
149                //String[] cards = In.readStrings ("data/cards.txt");
150                //StdRandom.shuffle (cards);
151
152                //StdIn.fromFile ("data/tiny.txt");
153                //StdIn.fromFile ("data/cards.txt");
154                StdIn.fromFile ("data/words3.txt");
155
156                String[] a = StdIn.readAllStrings();
157                sort(a);
158                show(a);
159
160                COUNT_OPS = true;
161                DoublingTest.run (20000, 5, N -> ArrayGenerator.integerRandomUnique (N),          (Integer[] x) -> sort (x));
162                DoublingTest.run (20000, 5, N -> ArrayGenerator.integerRandom (N, 2),             (Integer[] x) -> sort (x));
163                DoublingTest.run (20000, 5, N -> ArrayGenerator.integerPartiallySortedUnique (N), (Integer[] x) -> sort (x));
164        }
165}