$1$ Group Sorting $(67$ points$)$

We say that an array A of size n is k$-$group sorted if it can be divided into k consecutive groups,

each of size n$/$k$,$ such that the elements in each group are larger than the elements in earlier groups,

and smaller than elements in later groups. The elements within each group need not be sorted.

For example, the following array is $4-$group sorted:

$12437685101191215131614$

Note that every array is $1-$group$-$sorted, and only sorted arrays are n$-$group sorted. For the

rest of this problem we will only care about deterministic algorithms $($and lower bounds against

deterministic algorithms$).$ You may assume that all elements are distinct, and if you want to you

may assume that n and k are powers of $2.$

$($a$)(17$ points$)$ Describe an algorithm that k$-$group$-$sorts an array in O$($n log k$)($i$.$e$.,$ in at most

O$($n log k$)$ time it must turn an array which is not k$-$group sorted into one that is$).$ Prove

correctness and running time.

$($b$)(17$ points$)$ Prove that any comparison$-$based k$-$group$-$sorting algorithm requires $($n log k$)$

comparisons in the worst case.

$($c$)(16$ points$)$ Describe an algorithm that completely sorts an already k$-$group$-$sorted array in

O$($n log$($n$/$k$))$ time. Prove correctness and running time.

$($d$)(17$ points$)$ Prove that any comparison$-$based algorithm to completely sort an already k$-$groupsorted array requires $($n log$($n$/$k$))$ comparisons in the worst case.