001// Exercise 2.2.11 (Solution published at http://algs4.cs.princeton.edu/)
002package algs22;
003import stdlib.*;
004/* ***********************************************************************
005 *  Compilation:  javac MergeX.java
006 *  Execution:    java MergeX < 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 an
012 *  optimized version of mergesort.
013 *
014 *  % more tiny.txt
015 *  S O R T E X A M P L E
016 *
017 *  % java MergeX < tiny.txt
018 *  A E E L M O P R S T X                 [ one string per line ]
019 *
020 *  % more words3.txt
021 *  bed bug dad yes zoo ... all bad yet
022 *
023 *  % java MergeX < words3.txt
024 *  all bad bed bug dad ... yes yet zoo    [ one string per line ]
025 *
026 *************************************************************************/
027
028public class XMergeX {
029        private static final int CUTOFF = 7;  // cutoff to insertion sort
030
031
032        private static <T extends Comparable<? super T>> void merge(T[] src, T[] dst, int lo, int mid, int hi) {
033
034                // precondition: src[lo .. mid] and src[mid+1 .. hi] are sorted subarrays
035                assert isSorted(src, lo, mid);
036                assert isSorted(src, mid+1, hi);
037
038                int i = lo, j = mid+1;
039                for (int k = lo; k <= hi; k++) {
040                        if      (i > mid)              dst[k] = src[j++];
041                        else if (j > hi)               dst[k] = src[i++];
042                        else if (less(src[j], src[i])) dst[k] = src[j++];   // to ensure stability
043                        else                           dst[k] = src[i++];
044                }
045                if (COUNT_OPS) DoublingTest.addOps (hi-lo);
046
047                // postcondition: dst[lo .. hi] is sorted subarray
048                assert isSorted(dst, lo, hi);
049        }
050
051        private static <T extends Comparable<? super T>> void sort(T[] src, T[] dst, int lo, int hi) {
052                if (hi <= lo + CUTOFF) {
053                        insertionSort(src, lo, hi);
054                        return;
055                }
056                int mid = lo + (hi - lo) / 2;
057                sort(dst, src, lo, mid);
058                sort(dst, src, mid+1, hi);
059
060                /*
061        if (!less(dst[mid+1], dst[mid])) {
062            for (int i = lo; i <= hi; i++) src[i] = dst[i];
063            return;
064        }
065                 */
066                // a bit faster
067                if (!less(dst[mid+1], dst[mid])) {
068                        System.arraycopy(dst, lo, src, lo, hi - lo + 1);
069                        return;
070                }
071
072                merge(dst, src, lo, mid, hi);
073        }
074
075        public static <T extends Comparable<? super T>> void sort(T[] a) {
076                /*
077        Comparable[] aux = new Comparable[a.length];
078        for (int i = 0; i < a.length; i++)
079            aux[i] = a[i];
080                 */
081                // a bit faster
082                T[] aux = a.clone();
083                sort(a, aux, 0, a.length-1);
084
085                assert isSorted(a);
086        }
087
088
089        // sort from a[lo] to a[hi] using insertion sort
090        private static <T extends Comparable<? super T>> void insertionSort(T[] a, int lo, int hi) {
091                for (int i = lo; i <= hi; i++)
092                        for (int j = i; j > lo && less(a[j], a[j-1]); j--)
093                                exch(a, j, j-1);
094        }
095
096
097        // exchange a[i] and a[j]
098        private static <T> void exch(T[] a, int i, int j) {
099                if (COUNT_OPS) DoublingTest.incOps ();
100                T swap = a[i];
101                a[i] = a[j];
102                a[j] = swap;
103        }
104
105        // is a[i] < a[j]?
106        private static <T extends Comparable<? super T>> boolean less(T a, T b) {
107                if (COUNT_OPS) DoublingTest.incOps ();
108                return (a.compareTo(b) < 0);
109        }
110
111        /* *********************************************************************
112         *  Check if array is sorted - useful for debugging
113         ***********************************************************************/
114        private static <T extends Comparable<? super T>> boolean isSorted(T[] a) {
115                return isSorted(a, 0, a.length - 1);
116        }
117
118        private static <T extends Comparable<? super T>> boolean isSorted(T[] a, int lo, int hi) {
119                for (int i = lo + 1; i <= hi; i++)
120                        if (less(a[i], a[i-1])) return false;
121                return true;
122        }
123
124        // print array to standard output
125        private static <T> void show(T[] a) {
126                for (T element : a) {
127                        StdOut.println(element);
128                }
129        }
130
131        // test code
132        private static boolean COUNT_OPS = false;
133        public static void main(String[] args) {
134                StdIn.fromFile ("data/words3.txt");
135                String[] a = StdIn.readAllStrings();
136                sort(a);
137                show(a);
138
139                COUNT_OPS = true;
140                DoublingTest.run (20000, 5, N -> ArrayGenerator.integerRandomUnique (N),          (Integer[] x) -> sort (x));
141                DoublingTest.run (20000, 5, N -> ArrayGenerator.integerRandom (N, 2),             (Integer[] x) -> sort (x));
142                DoublingTest.run (20000, 5, N -> ArrayGenerator.integerPartiallySortedUnique (N), (Integer[] x) -> sort (x));
143
144        }
145}