10.3 Recursive Sorting
Just as recursion can be used to search data structures, it can be used to sort them. One of the most common recursive sorting algorithms is called merge sort.
A merge sort is a sort where the list is divided then merged back together in the correct order. This is done recursively as the list is repeatedly divided in half until it is only one item long. Then each of these lists gets combined back together in the correct order.
Merge sort starts at the top with the entire list, then it breaks this list into two halves.
It continues this process on both of the halves by breaking it down further. The halves continue to break down until they get to individual items.
Once it gets broken down, it then starts putting it back together in the correct order.
This occurs on each halve in the order that they appear in the array. To understand this fully, consider this visualization, which tracks the process that mergeSort
goes through as it sorts an array:
As it runs through, note how it only works on a portion of the items in the list. You can see how it works on the first half of the data, segment by segment. After completing the first half, the process is repeated on the second half before finally joining the two pieces together. As it joins the two halves, it moves each value from one half or the other into its final sorted place.
The merge sort is generally more efficient than the insertion sort or selection sort, and its performance is independent of the initial state of our array. In other words, a randomly sorted array and a nearly sorted array perform at the same speed.
The downside to the merge sort is that the implementation uses a fairly complex recursive algorithm. The implementation usually involves two methods - the merge sort method to break down the array and a helper method to reassemble it in the correct order.
Here is an implementation of mergeSort
:
The main purpose of this method is to break the array into smaller pieces, then when it can’t go any further, this method calls the merge method to start combining arrays. Using recursion, the base case is when there is only one element in the array. If the base case is not called, the middle part of this method creates two arrays, a left and a right, and puts half the current array into each of these new arrays. A recursive call is made with each half of the array.
When the base case is reached with an array length of 1, the recursive calls return. The method is then ready to combine the left and right array in the correct order. This is accomplished using the merge method:
The merge method takes the current array as well as the left and right arrays as input. It will then go through the two arrays to merge them. Notice that it doesn’t return anything. This is because the actual array object is passed to the method and updated. Changes can then be read in other methods.
The merge method walks through the next element in each array, determining if the left or right array has the smaller value, then inserting into the current array. Once it’s finished going through one of the arrays, there may still be elements remaining in either the left or right array. This last step adds any remaining elements to the end of the current array.
-
Incorrect
Correct
No Answer was selected
Invalid Answer
Which of the following is NOT true about a merge sort?
Merge sort is a complicated process, but what is it actually doing? We are going to take a closer look at the process in this exercise.
You are given the merge sort algorithm and you need to add some print statements so that you can see what actually is happening.
Add a print statement at each step, as well as print out the array each time. Your output needs to match the sample below. Here is a portion of a sort as an example: