Merge Sort

Problem statement

The problem is the same as in the Bubble Sort lesson. We are given an input array of numbers and we need to sort them. The only difference will be in the time complexity, which we will discuss later.

Solution

Suppose we had to sort an array A. A subproblem would be to sort a subsection of this array starting at index p and ending at index r, denoted as A[p…r].

• Divide — If q is the half-way point between p and r, we can split the subarray A[p…r] into two arrays A[p…q] and A[q+1, r].

• Conquer — In the conquer step, we try to sort both the subarrays A[p…q] and A[q+1, r]. If we haven’t yet reached the base case, we again divide both these subarrays and try to sort them.

• Combine — When the conquer step reaches the base step and we get two sorted subarrays A[p…q] and A[q+1, r] for array A[p…r], we combine the results by creating a sorted array A[p…r] from two sorted subarrays A[p…q] and A[q+1, r].

Let us visualize this to understand these operations better.