ANSWERS TO EXERCISES ON SORTING


 1. E  A  S  Y  Q  U  E  S  T  I  O  N
    A  E  S  Y  Q  U  E  S  T  I  O  N
    A  E  S  Y  Q  U  E  S  T  I  O  N
    A  E  S  Y  Q  U  E  S  T  I  O  N
    A  E  Q  S  Y  U  E  S  T  I  O  N
    A  E  Q  S  U  Y  E  S  T  I  O  N
    A  E  E  Q  S  U  Y  S  T  I  O  N
    A  E  E  Q  S  S  U  Y  T  I  O  N
    A  E  E  Q  S  S  T  U  Y  I  O  N
    A  E  E  I  Q  S  S  T  U  Y  O  N
    A  E  E  I  O  Q  S  S  T  U  Y  N
    A  E  E  I  N  O  Q  S  S  T  U  Y 
 

 2. E  A  S  Y  Q  U  E  S  T  I  O  N
    E  A  I  E  N* U  Y  S  T  S  O  Q
    E  A  E* I
    A* E
       E*
             I*
                N  O  Q* S  T  S  U  Y
                N  O*
                N*
                         S  T  S  U  Y*
                         S  T  S  U*
                         S  S* T
                         S*
                               T*
    A  E  E  I  N  O  Q  S  S  T  U  Y 


 3. N lg N. It divides the file in half because the partitioning
    pointers stop on keys equal to the partitioning element.


 4. E  A  S  Y  Q  U  E  S  T  I  O  N
    A  E
          S  Y
    A  E  S  Y
                Q  U
                      E  S
                E  Q  S  U
    A  E  E  Q  S  S  U  Y
                            I  T
                                  N  O
                            I  N  O  T
    A  E  E  I  N  O  Q  S  S  T  U  Y


 5. A  S  E  R  C  H  I  N  G  X  M  P
    A  S  E  R  H  C  I  N  G  X  M  P
    A  S  E  R  H  I  C  N  G  X  M  P
    A  S  E  R  H  I  N  C  G  X  M  P
    A  S  E  R  H  I  N  G  C  X  M  P
    A  S  E  R  H  I  N  G  X  C  M  P
    [numerous other answers]