Runtime of sorting a partially-sorted array

Question

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})$

Answer 1

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.

Answer 2

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

Answer 3

1. If the runtime would in fact be $O(k\log{k})$, then growing the array/increasing $n$ would not affect the runtime at all. This would imply that we could change the input in [1, n-k] (while still fulfilling the conditions) while the output must stay the same.
   $\implies$ Contradiction as the output depends on all array values.
2. The cost of sorting the subarray [n-k+1, n] is $O(k\log{k})$. Merging the subarrays [1, n-k] with [n-k+1, n] takes us $O(n)$.
   Thus the final runtime is $O(n + k\log{k})$.