Hi there, I was wondering if merge takes O(n) or O(nlogn) time as I've seen several different answers. Which is correct? Does merge work differently within a merge-sort leading to there being two values for complexity?

merge() is O(n) and mergesort() is O(n*log(n)). mergesort() repeatedly divides the array into subarrays until each subarray is size 1. This halving takes O(log(n)) steps and forms a complete binary tree with depth log(n). And for each level of division/depth in the binary tree, a merge() operation is called which merges the two halved arrays in sorted order. Since each element in the two subarrays are compared and placed at most once, there can be at most 2(n/2) = n operations for halves of size n, hence O(n). Thus, there are log(n) recursion levels, and for each level, a merge() operation of O(n) is called, which means overall is O(n*log(n)) operations.

Sorry, when you say it's overall O(N*logN) are you referring to a merge sort or a merge within a merge sort? The question I'm trying to figure out is: Explain the merge step of the mergesort algorithm. What is the overall complexity of merging in the mergesort algorithm for an input of size $n$? Explain your answer.

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.