merging logn + 1 sorted subarrays

Question

given array A of size $n$ which is made of $logn + 1$ sub arrays which are sorted, I need to sort ASAP.

example of array : $A[500,501,3,8,100,1,2,9]$ as you can see, sub arrays are :$[1:2][3:5][6:]$

my solution was: merge all logn + 1 arrays together, simultaneously.

so like I compare : $1:3:500$ >> append 1 to sorted array $2:3:500$ >> append 2 and so on until all is done.

i thought the complexity of my solution is expected to be $O(n)$ because each sub array on average has $\frac{n}{logn+1}$ values and there are $logn+1$ subarrays ..

chatgpt says its $O(nloglogn)$ ..

can you please explain the complexity analysis? does my solution even work?

Answer 1

I don't understand what "merge all $\log n + 1$ arrays together, simultaneously" means. The trivial algorithm that iteratively checks all the minima $m_1, m_2, \dots$ of the sub-arrays to find $j = \arg_{i=1, \dots, \log n +1} \min m_i$, adds $m_j$ to the final sorted array, and deletes $m_j$ from the $j$-th sub-array has complexity $\Theta(n \log n)$.

If instead you merge two arrays at a time, in a balanced binary-tree fashion, you have that each "level" of merging requires time $O(n)$ and that there are only $\log( \log n + 1) = O(\log \log n)$ levels. Hence the overall time-complexity is $O(n \log \log n)$.

Another solution is to just maintain a min-heap $H$ that stores the minima of the subarrays. Iteratively remove the minimum element $m$ from $H$ and add it to the final sorted array, then delete $m$ from its sub-array and insert the new minimum of that sub-array into $H$ (if any). Since $H$ can be built in linear-time (in its size), contains at most $\log n + 1$ elements throughout the execution of the algorithm, and each heap operation can be performed in time $O(\log |H|)$, where $|H|$ denotes the number of elements in $H$, it follows that the time complexity of this algorithm is also $O(n \log \log n)$.

Answer 2

Obviously you could pick the smallest number from the k arrays and remove it from its array, which is trivial to do in k steps, multiplied by the number of array elements.

Instead you split the array into pairs of two arrays, and find the smaller of each group, then you split the groups into pairs, each including 4 arrays, then 8, 16 arrays and so on. You find the smallest element instantly. Now in one of the groups of two one input has changed, so you find again which is smaller. Now the smallest of a group of 4 is changed, and the smallest of a group of 8 and so on, for a total of log k changes.

Total effort per element found is log k. Since you have k = log n, the total effort is n log log n.