  The normality measure $\mathcal{N}$ has been introduced by Mauduit and
S{\'a}rk{\"o}zy in order to describe the pseudorandomness properties of finite
binary sequences. Alon, Kohayakawa, Mauduit, Moreira and R{\"o}dl proved that
the minimal possible value of the normality measure of an $N$-element binary
sequence satisfies $$ (1/2 + o(1)) \log_2 N \leq \min_{E_N \in \{0,1\}^N}
\mathcal{N}(E_N) \leq 3 N^{1/3} (\log N)^{2/3} $$ for sufficiently large $N$.
In the present paper we improve the upper bound to $c (\log N)^2$ for some
constant $c$, by this means solving the problem of the asymptotic order of the
minimal value of the normality measure up to a logarithmic factor, and
disproving a conjecture of Alon \emph{et al.}. The proof is based on relating
the normality measure of binary sequences to the discrepancy of normal numbers
in base 2.
