Beginning Java Data Structures and Algorithms

Dividing the Problem

In the preceding section, we saw how we can use a recursive technique to split the problem into smaller multiple ones until the solution becomes easy to solve. Merge sort uses the same approach. The base case for our recursive technique is the same as quick sort. This is when the array is only one element long. When the array to sort only contains one item, the array is already sorted.

Figure 2.3 shows how merge sort array splitting occurs. At each step, we find the midpoint of the array and split the array in two. We then recursively sort the left and right part of the split array separately. We can stop the recursive call once the total elements to sort is equal to one as shown in the following figure:

Figure 2.3 Showing ...