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