Runtime of sorting a partially-sorted array
Your argument is not correct: Even if the subarrays a[0] to a [k-1], a [k] to a [2k-1] and so on are sorted, that doesn't make the whole array sorted. For example if k = 3 you could have [1, 2, 10000, 3, 4, 10001, 10002, 10003, 10004] and there's still a lot of sorting to be done. 

You basically have k sorted sequences of length about n/k, so you have k sequences to merge, which you should be able to do in O (n log k).