Running time for algorithm

Question

Let $n^+=k \cdot k$ be an integer. Let S be a list of $n$ elements that can be divided into $k$ smaller, sorted lists, $l_1, l_2,..,l_k$, where each of the $k$ small lists consists of $k$ elements. Let B be a doubly linked list consisting of $k$ pointers, $\{p_1, \dots p_k\}$, where each $p_i$ points to $l_i$.

What is the running time for S to be split into the smaller lists and B created?

Answer 1

$\Theta(n\log k)$.

Consider the quickest of sorting algorithms, the merge sort, with the following two modifications:

1. Since $\vert S\vert = k^2$, let our modified merge sort divide the given list S into $k$ equal parts and the recursion be called on each of them
2. At one point down the algorithm, each recursion has $k$ elements perfectly sorted, at which point further merging can be stopped. Each resulting array can be pointed to with a pointer, and we have the list B

Clearly, construction of B is a $\Theta(1)$ task well subsumed in the sorting task. The overall sorting recursion is then given by $T(n) = kT\left(\frac{n}{k}\right) + \mathcal{O}(n)$ which is found, using the Master Theorem, to have the time complexity of $\Theta(n\log n) = \Theta(n\log k^2) = \Theta(n\log k)$.