Overview of Merge Sort
Explore how merge sort applies the divide-and-conquer technique to sort arrays efficiently. Understand the process of dividing arrays into subarrays, recursively sorting them, and merging the sorted subarrays into a final sorted array. This lesson helps you grasp the core structure of merge sort and its base cases.
We'll cover the following...
We'll cover the following...
Because we're using divide-and-conquer to sort, we need to decide what our subproblems are going to look like. The full problem is to sort an entire array. Let's say that a subproblem is to sort a subarray. In particular, we'll think of a subproblem as sorting the subarray starting at index p and going through index r. It will be convenient to have a notation for a subarray, so let's say that