We design an efficient sublinear time parallel construction of optimal binary search trees. The efficiency of the parallel algorithm corresponds to its total work (the product $time \times processors$). Our algorithm works in $O(n^{1-\epsilon})\log(n)$ time with the total work $O(n^{2+2\epsilon})$, for an arbitrarily small constant $0 < \epsilon \leq \frac{1}{2}$. This is optimal within a factor $n^{2 \epsilon}$ with respect to the best known sequential algorithm given by Knuth, which needs only $O(n^2)$ time due to a {\it monotonicity} property of optimal binary search trees, see [6]). It is unknown how to explore this property in an efficient $NC$ construction of binary search trees. Here we show that it can be effectively used in sublinear time parallel computation. Our improvement also relies on the use (in independently processed small subcomputations) of the parallelism present in Knuth's algorithm. The best known sublinear time algorithms for the construction of binary search trees (as an instance of a more general problem) have $O(n^3)$ work for time larger than $n^{3/4}$, see [3] and [7]. For time $\sqrt{n}$ these algorithms need $n^{4}$ work, while our algorithm needs for this time only $n^3$ work, thus improving the known algorithms by a linear factor. Also if time is $O(n^{1-\epsilon})$ and $\epsilon$ is very small our improvement is close to $O(n)$. Such improvement is similar to the one implied by the $monotonicity$ property in sequential computations (from $n^3$ sequential time for a more general {\it dynamic programming} problem to $n^2$ time for the special case of optimal binary search trees).