Given an array A of size N, and also given a positive integer k,

where k < N, such that A[i] ≤ A[i + k] for all valid values of i within the array.

Develop a program to generate a new sorted array from the given array.

Constraints : (

i) Array size N will be read from user, and memory will be allocated at runtime.

Value of k will be also read from user.

(ii) The original array satisfying the condition A[i] ≤ A[i + k] for all valid values of i will be generated using random numbers.

(iii) Expected time complexity is O(Nlog2k) and expected space complexity is O(N + k),

including the memory required for the generated sorted array.

Try k-way merge. It takes only `O(N log k)`

time and `O(N + k)`

space. See https://code.google.com/p/kway/ for a very brief idea.

Here, `A[i+n*k]`

for `n`

=`0`

, `1`

, `2`

, `3`

, `...`

forms one (sorted) array (for all values of `i < k`

).