# 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

TrickDifficulty
LC 1395 Enumerate the middle element + Count #elements larger or smaller
6 points
LC 327 Prefix sum + Keep diff in range6-7 points
LC 493 Count #elements larger or smaller6 points
LC 315 Count #elements larger or smaller6 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;