3
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Thanks, your logic is simple and elegant, I wish I could accept two answers. $\endgroup$ – user4838962 Mar 20 '17 at 2:42
1
$\begingroup$
  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})$.
$\endgroup$
  • 1
    $\begingroup$ The number of permutations satisfying the given property is $N = \frac{n!}{(n/k)!^k}$, a multinomial coefficient corresponding to choosing which elements are in positions $A[j],A[k+j],\ldots,A[(n/k-1)k+j]$ for $j \in \{1,\ldots,n\}$. Stirling's approximation shows that $\log N \approx n\log n-k(n/k)\log(n/k) = n\log k$, hence $\Omega(n\log k)$ comparisons are needed in any comparison-based algorithm. $\endgroup$ – Yuval Filmus Mar 19 '17 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.