Minimum time for a partially sorted array?

Question

We are given a partially sorted array A, i.e. for i=1, 2, ..., nk , we have:

 A[i]<= A[i+k] 

To completely sort the array, we need at least O(n log k) time.

What is the condition and solution that make this axiom true always?

Answer 1

You can use shell sorting from this problem. In this algorithm, After each phase and some increment hk for each I, we have [i] ≤ a [i + hk]. all elements located at a distance hk from each other are sorted. This array is called hk-sorted. the shell sort output is sorted 1. if the array is k-sorted, then O (log k) for the sort array is required to sort the shell. each phase needs O (n), then the full order is O (n log k).

Suppose we want to sort this array:

this array is 4-sorted (k = 4). for sorting, this is necessary for 2 phases (h2 = 2, h3 = 1) Thus, two phases are required (log 4 or log k). On each phase there are n / k auxiliary arrays that need to be sorted. each sorting of auxiliary arrays with insertion sorting. The sort order of each auxiliary array is O (n). Finally, the full order is O (n * log k) = O (n log k).