The aim of our project was to implement a classic sorting algorithm utilizing concurrency. We decided on Merge Sort because of its inherent parallelism. Sorting in general has been hailed as a cornerstone in Computer Science [SHG09], as many computer algorithms rely heavily upon it. Such an algorithm is for example the classic Kruskal algorithm for constructing a minimum spanning tree of an undirected graph [Kru56]. Merge Sort is based on the popular Divide-and-conquer approach [CLR02], where the problem at hand is broken into smaller problems of similar nature, which are in turn solved recursively, and the solutions are then combined.
Parallel Merge Sort