The optimal algorithm to sort your array in a decision-tree model takes time $\Theta(n \log k)$. One arrow is trivial, an algorithm that sorts $A$ in time $O(n \log k)$ is, for example, mergesort.
The other arrow is more interesting. Assume, for the sake of simplicity, that $n$ is an integer multiple of $k$ and that $\lambda = n/k$. First of all, unwinding your condition we get:
- $A[1] \le A[k+1] \le A[2k+1] \dots \le A[(\lambda-1)k + 1]$
- $A[2] \le A[k+2] \le A[2k+2] \dots \le A[(\lambda-1)k + 2]$
- $\dots$
- $A[k] \le A[2k] \le A[3k] \dots \le A[n]$
Observe that no other conditions are imposed on the elements of $A$, therefore any permutation of $\{1 \dots n\}$ that satisfies those conditions is a valid starting state for $A$.
Now, let's count how many such permutations are there. This is equivalent to asking in how many ways we can choose $\lambda$ elements from $n$ to be assigned to the first subarray, then $\lambda$ elements from the remaining $n - \lambda$ to be assigned to the second and so on. We can compute this number in the following way:
$$
N = \prod_{j=0}^{k-1} \binom{n-j\lambda}{\lambda}
= \prod_{j=0}^{k-1} \frac{(n-j)!}{\lambda!(n-j-\lambda)!}
= \frac{1}{\lambda!^k} \prod_{j=0}^{k-1} \frac{(n-j)!}{(n-j-\lambda)!}
= \frac{n!}{\lambda!^k}
$$
Since we assumed that we are working in a decision-tree model, sorting $A$ requires a number of comparisons bounded by:
$$
\Omega\left(\log \frac{n!}{\lambda!^k} \right) =
\Omega\left( n \log n - k \frac{n}{k} \log \frac{n}{k} \right) =
\Omega \left(n \log \frac{nk}{n} \right) = \Omega(n \log k)
$$
Which proves our assertion.