Sorting an already k-sorted array
You have the right idea but I think you are overthinking it a bit.

For a), your teacher had a good hint.   I think there is a simpler solution than the way you are going. As a further hint, notice that if $k=2$, the problem is solved after 1 round of quicksort (with linear median-finding).  You have two equal-sized subarrays, where the left is smaller than the right.  Can you extend this to $k=4$?  Then, can you extend it to arbitary $k$?

b) I think you have the right intuition, but this argument is not formal yet.  Recall the original proof of the sorting lower bound, where you argue that you need $n\log n$ comparisons to get  $n!$ permutations.  Can you extend that to this case?  How many permutations are required when we don't need to fully sort?