3 ms·
You end up with N lists to merge, so to find the smallest head at each given time, you'd take log(N) steps. Given that you have N^2 elements, it would take a t
by karpierz 5y ago
You end up with N lists to merge, so to find the smallest head at each given time, you'd take log(N) steps.
Given that you have N^2 elements, it would take a total of N^2 log(N) time, which is equivalent in time complexity to simply sorting a list with N^2 elements.
- bobthepanda 5y agoHm. that's fair. Just append them altogether and apply timsort, I guess, or some other sort that identifies runs well.