Runtime of sorting a partially-sorted array

I have an array of $n$ items which is partially sorted like below:

$$A[i]\le{A[i+k]}$$

where:

$$i=1,2,...,n-k$$

For sorting the array completely, I wonder what the runtime big O is.

I feel only an array of size $k$ needs to be sorted. Because if the sub-array $A[1\le{i}\le{k}]$ is sorted, then all the subsequent sub-arrays are automatically sorted: $A[1+k\le{i}\le{2k}]$ and $A[1+2k\le{i}\le{3k}]$ up to $A[n-k\le{i}\le{n}]$

Therefore the runtime big O might be just $O(k\log{k})$

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).

StackExchange Computer Science Q#71761, answer score: 6