Can anyone explain !! How the complexity of building the merge sort is O(nlog(n)) . As if we build segment tree for maximum query it will take O(n) time because we had to cover approx 2*n to 4*n nodes and at each node merging two children nodes took O(1) time. But here in merge sort merging two children nodes takes O(n) time . So how come the complexity is O(nlog(n))?