1 Sorting
Sorting.java
Java Threads
Operating Systems
Lab Sheet Week 4 – Model Solutions
1
MergeTask.java
SortTask.java
Reflections:
5. A sequential sorting algorithm has complexity O(n log n) where n is the length of the input
list. The merge operation has complexity O(n). In the multithreaded version, the sorting
of the two parts can be done in parallel followed by the merging. This reduces the runtime
to n log n +n. For a list of size 106, this is a reduction from 6·106 to roughly 3.85·106. The 22
merge operation has lower complexity than a sorting algorithm. Some sorting algorithms such as QuickSort randomly shuffle the inputs before sorting (to avoid the O(n2) worst case), rendering the previous sorting of the two parts useless.
6. Answer given in 7.