Merge Sort

Summary

In this post, I will introduce some problems using the merge sort technique.

These problems often ask, for an element at index , how many are there which satisfies a formula.

OJ

	Trick	Difficulty
LC 1395	Enumerate the middle element + Count #elements larger or smaller	6 points
LC 327	Prefix sum + Keep diff in range	6-7 points
LC 493	Count #elements larger or smaller	6 points
LC 315	Count #elements larger or smaller	6 points

Details

The Master Theorem

   

If is of complexity , then is of complexity

So in these problems, a key point is to keep the merge part of complexity by leveraging the sorted property.

Keep Difference in Range

I want to talk about the merge part of LC 327 in this section. Given two sorted array and , the problem is to count how many are there, such that

   

Usually, we will enumerate the left part (or the right part) by . We use two cursors and to store the boundary in the right part to satisfy the above formula.

int mid = left + (right - left) / 2;
int result = merge_sort(left, mid, nums) + merge_sort(mid + 1, right, nums);
int start = mid + 1, end = mid + 1;
for (int i = left; i < mid + 1; ++i) {
    while (start < right + 1 && (long)nums[start] - nums[i] < lower) {
        start++;
    }
    while (end < right + 1 && (long)nums[end] - nums[i] <= upper) {
        end++;
    }
    result += (end - start);
}
inplace_merge(nums.begin() + left, nums.begin() + mid + 1, nums.begin() + right + 1);
return result;