Difference between revisions of "MergeSort"
Benjaminchoi (talk | contribs) (Created page with "=Background= In computer science, merge sort refers to a sorting algorithm which splits an array of data into continuously smaller halves until the arrays reach a size of 1,...") |
|||
| (2 intermediate revisions by the same user not shown) | |||
| Line 2: | Line 2: | ||
In computer science, merge sort refers to a sorting algorithm which splits an array of data into continuously smaller halves until the arrays reach a size of 1, after which the elements are continuously compared and merged into a sorted array. For more information on how this process works, visit [https://en.wikipedia.org/wiki/Merge_sort this] page. If you took CSE 247, this algorithm should look extremely familiar to you. | In computer science, merge sort refers to a sorting algorithm which splits an array of data into continuously smaller halves until the arrays reach a size of 1, after which the elements are continuously compared and merged into a sorted array. For more information on how this process works, visit [https://en.wikipedia.org/wiki/Merge_sort this] page. If you took CSE 247, this algorithm should look extremely familiar to you. | ||
| + | |||
| + | ==Visualization== | ||
| + | |||
| + | If you've never seen mergesort before, it may be helpful to take a look at [https://visualgo.net/en/sorting?slide=10 this] page which gives a visual demonstration of the algorithm in practice. | ||
=Where to Start= | =Where to Start= | ||
| − | Navigate to the ''' | + | Navigate to the '''sort.studio.merge''' package and look at the <code>MergeSort.java</code> class. The '''sort.core.merg''' packagecontains some useful building block classes we created for you. Take a look at <code>MergeableData</code> interface as you will need to use its methods to assist you in this studio. |
=MergeSort Studio= | =MergeSort Studio= | ||
Revision as of 17:30, 13 September 2017
Contents
Background
In computer science, merge sort refers to a sorting algorithm which splits an array of data into continuously smaller halves until the arrays reach a size of 1, after which the elements are continuously compared and merged into a sorted array. For more information on how this process works, visit this page. If you took CSE 247, this algorithm should look extremely familiar to you.
Visualization
If you've never seen mergesort before, it may be helpful to take a look at this page which gives a visual demonstration of the algorithm in practice.
Where to Start
Navigate to the sort.studio.merge package and look at the MergeSort.java class. The sort.core.merg packagecontains some useful building block classes we created for you. Take a look at MergeableData interface as you will need to use its methods to assist you in this studio.
MergeSort Studio
You will need to implement merge sort sequentially and in parallel, but you will need to do both implementations recursively. The kernel method should call itself using recursion, but the mergesort method should only call the kernel once. We do this in order to manipulate where we can place our async/finish blocks. When running recursively, we do not want to place a finish block around the recursive call as that would defeat the purpose of calling an async in the first place. When completing this studio, think carefully about where to put your async/finish calls.
Sequential Implementation
The only thing you will need to edit is the kernel method. As this is a sequential implementation, there is no need to call an async or finish. Using the description of merge sort provided to you in the background, try to consider what the base case would be. Then, further consider how to call the method recursively. When the array reaches the base case, you will need to complete the “merging” aspect of merge sort. As mentioned above, there is a method in the utils class that should help with this.
Hint: Follow the Wikipedia links and look at the pseudocode for help.
Parallel Implementation
This should look exactly like the sequential implementation, but it should also include async/finish calls. Think carefully about where to place them to maximize concurrency.
