  Block Sorting is a well studied problem, motivated by its applications in
Optical Character Recognition (OCR), and Computational Biology. Block Sorting
has been shown to be NP-Hard, and two separate polynomial time 2-approximation
algorithms have been designed for the problem. But questions like whether a
better approximation algorithm can be designed, and whether the problem is
APX-Hard have been open for quite a while now.
  In this work we answer the latter question by proving Block Sorting to be
Max-SNP-Hard (APX-Hard). The APX-Hardness result is based on a linear reduction
of Max-3SAT to Block Sorting. We also provide a new lower bound for the problem
via a new parametrized problem k-Block Merging.
