Merging one single layer is O(n) because each element is processed once. Since this needs to be done log n times, because there are log n 'layers' in the tree created when subdividing the list, the overall complexity of merging is O(n log n). At least that's how I understand it.