0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ What is $n$? What does the following sentence mean "each sub array on average is $\frac{n}{\log n + 1}$"? How can a sub-array be a number, or a function? What are you taking the average over? $\endgroup$
    – Steven
    Commented Feb 25, 2023 at 10:37
  • $\begingroup$ edited your questions @Steven $\endgroup$
    – WalaWizon
    Commented Feb 25, 2023 at 16:08

2 Answers 2

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ thank you very much!about the heap solution: you mean I build a min heap and it has the minimal value in each subarray at any given moment? and when I extract-min / just remove the root and heapify I put the next in line in the subarray from which the root was?(cuz each subarray is sorted)? $\endgroup$
    – WalaWizon
    Commented Feb 25, 2023 at 18:30
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.