content: /***********************************************************************************
   *  Compilation: javac Quick3string.java
   *  Execution:   java Quick3string < input.txt
   *
   *  Reads string from standard input and 3-way string quicksort them.
   *
   *  % java Quick3string < shell.txt
   *  are
   *  by
   *  sea
   *  seashells
   *  seashells
   *  sells
   *  sells
   *  she
   *  she
   *  shells
   *  shore
   *  surely
   *  the
   *  the
   *
   ***********************************************************************************/
  
  public class Quick3string {
      private static final int CUTOFF =  15;   // cutoff to insertion sort
  
      // sort the array a[] of strings
      public static void sort(String[] a) {
          // StdRandom.shuffle(a);
          sort(a, 0, a.length-1, 0);
          assert isSorted(a);
      }
  
      // return the dth character of s, -1 if d = length of s
      private static int charAt(String s, int d) { 
          assert d >= 0 && d <= s.length();
          if (d == s.length()) return -1;
          return s.charAt(d);
      }
  
  
      // 3-way string quicksort a[lo..hi] starting at dth character
      private static void sort(String[] a, int lo, int hi, int d) { 
  
          // cutoff to insertion sort for small subarrays
          if (hi <= lo + CUTOFF) {
              insertion(a, lo, hi, d);
              return;
          }
  
          int lt = lo, gt = hi;
          int v = charAt(a[lo], d);
          int i = lo + 1;
          while (i <= gt) {
              int t = charAt(a[i], d);
              if      (t < v) exch(a, lt++, i++);
              else if (t > v) exch(a, i, gt--);
              else              i++;
          }
  
          // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]. 
          sort(a, lo, lt-1, d);
          if (v >= 0) sort(a, lt, gt, d+1);
          sort(a, gt+1, hi, d);
      }
  
      // sort from a[lo] to a[hi], starting at the dth character
      private static void insertion(String[] a, int lo, int hi, int d) {
          for (int i = lo; i <= hi; i++)
              for (int j = i; j > lo && less(a[j], a[j-1], d); j--)
                  exch(a, j, j-1);
      }
  
      // exchange a[i] and a[j]
      private static void exch(String[] a, int i, int j) {
          String temp = a[i];
          a[i] = a[j];
          a[j] = temp;
      }
  
      // is v less than w, starting at character d
      private static boolean less(String v, String w, int d) {
          assert v.substring(0, d).equals(w.substring(0, d));
          return v.substring(d).compareTo(w.substring(d)) < 0; 
      }
  
  
      // is the array sorted
      private static boolean isSorted(String[] a) {
          for (int i = 1; i < a.length; i++)
              if (a[i].compareTo(a[i-1]) < 0) return false;
          return true;
      }
  
  
      public static void main(String[] args) {
  
          // read in the strings from standard input
          String[] a = StdIn.readStrings();
          int N = a.length;
  
          // sort the strings
          sort(a);
  
          // print the results
          for (int i = 0; i < N; i++)
              StdOut.println(a[i]);
      }
  }
  