Merge Sort and Divide and Conquer

Opening scenario

Merge k Sorted Lists (LC 23). Given k sorted linked lists, merge them into one sorted list. The classic companion that exposes merge sort's hidden power: Count of Range Sum (LC 327) — count subarrays whose sum lies in [lower, upper]. The foundational warm-up is count inversions in an array: count the pairs i < j where nums[i] > nums[j].

LC numbers identify LeetCode problems.

Start with merging two sorted lists: repeatedly take the smaller current head. Then consider how to organize repeated two-list merges so a node is not rescanned unnecessarily. The linked-list examples reuse the original nodes and therefore change their links.

Question progression

Q1 — Why split at all? What does "divide and conquer" buy over a single pass?

Question: To sort an array you could insert elements one by one (O(n^2)). Merge sort instead splits in half, sorts each half, merges. Why is splitting the win, and what's the recurrence?