001package algs22;
002import stdlib.*;
003/* ***********************************************************************
004 *  Compilation:  javac MergeBU.java
005 *  Execution:    java MergeBU < input.txt
006 *  Dependencies: StdOut.java StdIn.java
007 *  Data files:   http://algs4.cs.princeton.edu/22merge/tiny.txt
008 *                http://algs4.cs.princeton.edu/22merge/words3.txt
009 *
010 *  Sorts a sequence of strings from standard input using
011 *  bottom-up mergesort.
012 *
013 *  % more tiny.txt
014 *  S O R T E X A M P L E
015 *
016 *  % java MergeBU < 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 MergeBU < words3.txt
023 *  all bad bed bug dad ... yes yet zoo    [ one string per line ]
024 *
025 *************************************************************************/
026
027public class MergeBU {
028
029        // stably merge a[lo..m] with a[m+1..hi] using aux[lo..hi]
030        private static <T extends Comparable<? super T>> void merge(T[] a, T[] aux, int lo, int m, int hi) {
031
032                // copy to aux[]
033                for (int k = lo; k <= hi; k++) {
034                        aux[k] = a[k];
035                }
036
037                // merge back to a[]
038                int i = lo, j = m+1;
039                for (int k = lo; k <= hi; k++) {
040                        if      (i > m)                a[k] = aux[j++];
041                        else if (j > hi)               a[k] = aux[i++];
042                        else if (less(aux[j], aux[i])) a[k] = aux[j++];
043                        else                           a[k] = aux[i++];
044                }
045                if (COUNT_OPS) DoublingTest.addOps (hi-lo);
046
047        }
048
049        // bottom-up mergesort
050        @SuppressWarnings("unchecked")
051        public static <T extends Comparable<? super T>> void sort(T[] a) {
052                int N = a.length;
053                T[] aux = (T[]) new Comparable[N];
054                for (int n = 1; n < N; n = n+n) {
055                        for (int i = 0; i < N-n; i += n+n) {
056                                int lo = i;
057                                int m  = i+n-1;
058                                int hi = Math.min(i+n+n-1, N-1);
059                                merge(a, aux, lo, m, hi);
060                        }
061                }
062                assert isSorted(a);
063        }
064
065        /* *********************************************************************
066         *  Helper sorting functions
067         ***********************************************************************/
068
069        // is v < w ?
070        private static <T extends Comparable<? super T>> boolean less(T v, T w) {
071                if (COUNT_OPS) DoublingTest.incOps ();
072                return (v.compareTo(w) < 0);
073        }
074
075
076        /* *********************************************************************
077         *  Check if array is sorted - useful for debugging
078         ***********************************************************************/
079        private static <T extends Comparable<? super T>> boolean isSorted(T[] a) {
080                for (int i = 1; i < a.length; i++)
081                        if (less(a[i], a[i-1])) return false;
082                return true;
083        }
084
085        // print array to standard output
086        private static <T> void show(T[] a) {
087                for (T element : a) {
088                        StdOut.println(element);
089                }
090        }
091
092        // test code
093        private static boolean COUNT_OPS = false;
094        public static void main(String[] args) {
095                StdIn.fromFile ("data/words3.txt");
096
097                String[] a = StdIn.readAllStrings();
098                sort(a);
099                show(a);
100
101                COUNT_OPS = true;
102                DoublingTest.run (20000, 5, N -> ArrayGenerator.integerRandomUnique (N),          (Integer[] x) -> sort (x));
103                DoublingTest.run (20000, 5, N -> ArrayGenerator.integerRandom (N, 2),             (Integer[] x) -> sort (x));
104                DoublingTest.run (20000, 5, N -> ArrayGenerator.integerPartiallySortedUnique (N), (Integer[] x) -> sort (x));
105        }
106}
107
108