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.