Given $n$ arrays of size $k$ each, we want to show that at least $\Omega(nk \log k)$ comparisons are needed to sort all arrays (indepentent of each other).
My proof is a simple modification of the decision tree argument used to obtain the lower bound for comparison-based sorting of one array. More specifically, I argue that there are in total $k!^n$ possible permutations for the entries in all given arrays, and that a binary tree with that number of leaves is of height $h \in \Omega(nk \log k)$. Is that argument correct?
Furthermore, I was told that merely observing that one needs $\Omega(k \log k)$ comparisons for each of the arrays and we need to sort $n$ times in total (for $n$ arrays) is not a sufficient argument. Why is that? My answer would be that this is just one possible approach to this problem, and not a general argument excluding each and every other potential comparison-based algorithm for solving the given task with less than $\Omega(nk \log k)$ comparisons. However, this is not particularly concise and I would consider a rather technical argument (which I don't see) as more appropriate. What would that be?