SWEN-342 Concurrent & Distributed Software Systems

Concurrent Merge Sort

The Problem

For this activity you will implement a concucrent merge sort using Akka typed Actors.

Requiements

1. Your implementation must use typed.Actors for all of the algorithm steps and processing.
2. The algorithm is required to work with int arrays.
3. 5 Point Bonus if your solution will work with a generic array.
4. For output, the program should print the first and last 5 elements of the array being sorted, both before it was sorted and after the sort.
5. You should have at least one file named MergeSort, though you may write other helper classes/files.

Example Output

Test array is an array with elements from 100000 - 1

        Starting Array: 100000, 99999, 99998, 99997, 99996 ... 5, 4, 3, 2, 1
        Sorted Array: 1, 2, 3, 4, 5 ... 99996, 99997, 99998, 99999, 100000

Hints

1. I would recommend making sure you are using the latest version of Akka. See the Maven Module info at the top of this page.
2. The actor system does not output errors to the terminal, it silently catches them. For this reason, more than any other activity, it is very important that you create your implementation in very small segments.
3. Your solution should be able to sort an array of 100000 elements nearly instantaneously. If it takes more than a couple seconds, there is most likely an error in the way the algorithm was implemented.

Merge Sort Algorithm

define merge_sort(an_array)
  if an_array has at most 1 element
     return an_array
  otherwise
    - split an_arry into two halves whose sizes differ by at most 1
    - recursively merge_sort each half
    - merge the two sorted halves
    - return the merged result

define merge(sorted1, sorted2)
    result = Array()
    i1 = 0
    i2 = 0
    while i1 < len(sorted1) and
          i2 < len(sorted2)
      if sorted1[i1] <= sorted2[i2]
        add sorted1[i1] to result
        i1 = i1 + 1
      otherwise
        add sorted2[i2] to result
        i2 = i2 + 1
    if i1 < len(sorted1)
      add rest of sorted1 to result
    otherwise if i2 < len(sorted2)
      add rest of sorted2 to result
    return result

Deliverables

Commit and push your solution to the GitHub repository by the due date.