Assignment: Merge Sort and Applications
Objective
Explore advanced applications of Merge Sort through a series of algorithmic problems. The
following LeetCode problems demonstrate how Merge Sort’s divide-and-conquer paradigm
can be leveraged not just for sorting but also for solving complex counting problems effi-
ciently.
Instructions
• Attempt all five problems listed below.
• You may use Merge Sort or its modifications as discussed in class.
• Submit a brief explanation with your code describing how Merge Sort is used in each
solution.
Problems
Problem 1: Count of Smaller Numbers After Self
• Link: LeetCode #315
• Description: For each element in the array, count how many smaller
elements are to its right.
• Merge Sort Relevance: Solved efficiently by modifying merge sort to
track counts during the merge step.
• Difficulty: Medium–Hard
Problem 2: Sort an Array
• Link: LeetCode #912
• Description: Implement an efficient sorting algorithm.
• Merge Sort Relevance: Direct application — implement merge sort
from scratch.
• Difficulty: Medium
1
Problem 3: Reverse Pairs
• Link: LeetCode #493
• Description: Count the number of reverse pairs where i < j and nums[i] >
2 · nums[j].
• Merge Sort Relevance: Use a modified merge sort to count these effi-
ciently during merging.
• Difficulty: Medium
Problem 4: Count of Range Sum
• Link: LeetCode #327
• Description: Count the number of range sums that lie within a given
inclusive range.
• Merge Sort Relevance: Use prefix sums and merge sort to count valid
sums during merge steps.
• Difficulty: Medium–Hard
Problem 5: Kth Smallest Pair Distance
• Link: LeetCode #719
• Description: Given an array, find the k-th smallest distance between all
pairs.
• Merge Sort Relevance: Often solved with binary search and a merge-
sort-like counting routine.
• Difficulty: Medium
Tip: These problems go beyond sorting. Try to understand how merging and divide-and-
conquer help solve problems that involve counting and ordering relationships.