Multithreaded Merge Sort
Explore how to implement merge sort using multiple threads in Java. This lesson covers the recursive divide and conquer approach, explains the running time with recurrence relations, and demonstrates parallelizing the sort to improve efficiency on large datasets. Understand how to safely divide work into concurrent tasks without synchronization issues.
We'll cover the following...
Merge Sort
Merge sort is a typical text-book example of a recursive algorithm and the poster-child of the divide and conquer strategy. The idea is very simple, we divide the array into two equal parts, sort them recursively and then combine the two sorted arrays. The base case for recursion occurs when the size of the array reaches a single element. An array consisting of a single element is already sorted.
The running time for a recursive solution is expressed as a recurrence equation. An equation or inequality that describes a function in terms of its own value on smaller inputs is called a recurrence equation. The running time for a recursive algorithm is the solution to the recurrence equation. The recurrence equation for recursive algorithms usually takes on the following form:
Running Time = Cost to divide into n subproblems + n * ...