Merge Sort
The merge sort algorithm, another recursive sort algorithm, sorts a list by recursively dividing the list in half until each sublist has one element and then recombining these sublists in order.
General Strategy:
• Begin by dividing the list in two roughly equal parts and then recursively calling itself with each of those lists.
• Continue the recursive decomposition of the list until the base case of the recursion is reached, where the list is divided into lists of length one, which are by definition sorted.
• Then, as control passes back up the recursive calling structure, the algorithm merges into one sorted list the two sorted sublists resulting from the two recursive calls.
Example:
Let’s look at the recursive decomposition portion of the algorithm.
The merge portion of the algorithm would then recombine the list.
Assignment
1. The merge sort: Trace the indices for the given data:
int[] grades = {3,2,5,2};
Is it a stable sort? Explain
Use the code to supports your answer.
Good resources:
These are two good video with details and mathematical analysis: