Mergesort always makes recursive calls to sort subarrays that are about half size of the original array, resulting in O(n log n) time.